def bfs(cost, s, d, c)
  n = cost.size
  memo = Array.new(n){Array.new(c+1, 5000000)}
  memo[s][c] = 0
  q = Array.new.push([s, c])
  until q.empty? do
    town, ticket = q.pop
    n.times do |nextTown|
      next unless cost[town][nextTown]
      nextCost = memo[town][ticket] + cost[town][nextTown]
      if nextCost < memo[nextTown][ticket]
        memo[nextTown][ticket] = nextCost
        q.push([nextTown, ticket])
      end
      next if ticket == 0
      nextCost = memo[town][ticket] + cost[town][nextTown]/2
      if nextCost < memo[nextTown][ticket-1]
        memo[nextTown][ticket-1] = nextCost
        q.push([nextTown, ticket-1])
      end
    end
  end
  memo[d].min
end

until (c,n,m,s,d=gets.split.map(&:to_i)).all?(&:zero?) do
  cost = Array.new(n) {Array.new(n)}
  m.times do
    a, b, f = gets.split.map(&:to_i)
    cost[a-1][b-1] = cost[b-1][a-1] = f
  end
  p bfs(cost, s-1, d-1, c)
end