require "set"

INF = (1 << 31) - 1
TownMax = 100

until (given = gets.chomp) == "0 0 0 0 0"
  c, n, m, s, d = given.split.map(&:to_i)
  s -= 1
  d -= 1
  data = m.times.map {gets.split.map(&:to_i)}
  
  fares = Array.new(n) {[]}
  route_map = Array.new(n, [])
  towns = Set.new
  
  data.each do |a, b, f|
    a -= 1
    b -= 1
    route_map[a] += [b]
    route_map[b] += [a]
    fares[a][b] = f
    fares[b][a] = f
    towns << a
    towns << b
  end
  
  shortest = Array.new(c + 1) {Array.new(TownMax, INF)}
  done = Array.new(c + 1) {Array.new(TownMax, false)}
  
  shortest[0][s] = 0
  
  loop do
    u0 = u1 = nil
    (c + 1).times do |ticket|
      towns.each do |town|
        next if done[ticket][town]
        if !u0 or shortest[ticket][town] < shortest[u0][u1]
          u0, u1 = ticket, town
        end
      end
    end
    break unless u0
    done[u0][u1] = true
    
    route_map[u1].each do |to|
      if (a0 = shortest[u0][u1] + fares[u1][to]) < shortest[u0][to]
        shortest[u0][to] = a0
      end
      if u0 + 1 <= c
        if (a1 = shortest[u0][u1] + fares[u1][to] / 2) < shortest[u0 + 1][to]
          shortest[u0 + 1][to] = a1
        end
      end
    end
  end
  
  puts shortest.map {|a| a[d]}.min
end
