def update q, total, i, cost, remain
  q << [i, cost, remain]
  total[remain][i] = [total[remain][i], cost].min
end

def bfs dist, start, dest, ticket
  n = dist.size
  total = Array.new(ticket + 1).map{Array.new(n, 1000000)}
  q = Array.new
  q << [start, 0, ticket]
  
  while ! q.empty?
    pos, sum, remain = q.delete_at(0)
    return sum if pos == dest
    n.times do |i|
      next if dist[pos][i] == -1
      cost = sum + dist[pos][i]
      costWithTicket = sum + dist[pos][i] / 2
      if remain > 0 && (costWithTicket < total[remain - 1][i])
        update q,total,i,costWithTicket,remain - 1
      end
      if cost < total[remain][i]
        update q,total,i,cost,remain
      end
    end
    q.sort!{|e1, e2| e1[1] <=> e2[1]}
  end
end

loop do
  c,n,m,s,d = $stdin.gets.chomp.split(" ").map(&:to_i)
  break if (c|n|m|s|d == 0)
  dist = Array.new(n).map{Array.new(n, -1)}
  m.times do
    a,b,f = $stdin.gets.chomp.split(" ").map(&:to_i)
    dist[a - 1][b - 1] = f
    dist[b - 1][a - 1] = f
  end
  p bfs(dist, s - 1, d - 1, c)
end