import scala.collection.mutable

object Main extends App {

  import scala.io.StdIn._

  solve
  def solve: Unit = {
    val Array(c, n, m, s, d) = readLine.trim.split(' ').map(_.toInt)
    if (n == 0) return
    val towns = Array.tabulate(n){_ ⇒ Nil: List[(Int, Int)]}
    for (_ ← 0 until m){
      val Array(a, b, f) = readLine.trim.split(' ').map(_.toInt)
      towns(a - 1) ::= (b - 1, f)
      towns(b - 1) ::= (a - 1, f)
    }
    val minCost = Array.tabulate(c + 1){_ ⇒ Array.tabulate(n){_ ⇒ Int.MaxValue}}.also{a ⇒ a(c)(s - 1) = 0}
    val queue = mutable.PriorityQueue()(Ordering.by[(Int, Int, Int), Int](_._3).reverse).also{q ⇒ q.enqueue((c, s - 1, 0))}
    while (queue.nonEmpty){
      val (rest, current, cost) = queue.dequeue()
      if (minCost(rest)(current) == cost){
        for ((next, c) ← towns(current)) {
          if (minCost(rest)(next) > cost + c){
            minCost(rest)(next) = cost + c
            queue.enqueue((rest, next, cost + c))
          }
          if (rest > 0 && minCost(rest - 1)(next) > cost + c / 2){
            minCost(rest - 1)(next) = cost + c / 2
            queue.enqueue((rest - 1, next, cost + c / 2))
          }
        }
      }
    }
    println((0 to c).map(i ⇒ minCost(i)(d - 1)).min)
    solve
  }
  implicit class Extension[T](val value :T) extends AnyVal {
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
    @inline
    def also(@inline func: T ⇒ Unit): T = {func(value); value}
  }
}
