Go: package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	NowPosition          int
	DiscountTicketTCount int
	Amount               int
}

type PriorityQueueNode []*Node

func (pq PriorityQueueNode) Len() int {
	return len(pq)
}

func (pq PriorityQueueNode) Less(i, j int) bool {
	return pq[i].Amount < pq[j].Amount
}

func (pq PriorityQueueNode) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueueNode) Push(node interface{}) {
	*pq = append(*pq, node.(*Node))
}

func (pq *PriorityQueueNode) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

type Point struct {
	NextPoint int
	Fee       int
}

func main() {
	var c, n, m, s, d int
	var a, b, f int

	for {
		fmt.Scan(&c, &n, &m, &s, &d)
		if c == 0 && n == 0 && m == 0 && s == 0 && d == 0 {
			break
		}
		s--
		d--
		pointMap := make([][]Point, n)
		for i := 0; i < n; i++ {
			pointMap[i] = make([]Point, 0)
		}
		for i := 0; i < m; i++ {
			fmt.Scan(&a, &b, &f)
			a--
			b--
			pointMap[a] = append(pointMap[a], Point{NextPoint: b, Fee: f})
			pointMap[b] = append(pointMap[b], Point{NextPoint: a, Fee: f})
		}
		pq := make(PriorityQueueNode, 0)
		start := Node{NowPosition: s, DiscountTicketTCount: c, Amount: 0}
		heap.Push(&pq, &start)
		for len(pq) != 0 {
			now := heap.Pop(&pq).(*Node)
			if now.NowPosition == d {
				fmt.Println(now.Amount)
				break
			}
			for _, v := range pointMap[now.NowPosition] {
				next := &Node{v.NextPoint, now.DiscountTicketTCount, now.Amount + v.Fee}
				heap.Push(&pq, next)
				if now.DiscountTicketTCount > 0 {
					next = &Node{v.NextPoint, now.DiscountTicketTCount - 1, now.Amount + v.Fee/2}
					heap.Push(&pq, next)
				}
			}
		}
	}
}

C++: #include <vector>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <queue>
#include <string.h>
#include <stdio.h>

typedef long long ll;
using namespace std;

typedef vector<vector<pair<int, int> > > graph_t;
typedef vector<tuple<int, int, int>> edges_t;
const int INF = 1e9+1;

vector<int> dijkstra(int N, const graph_t &g, int s)
{
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
	vector<int> cost(N, INF);
	q.push(make_pair(0, s));
	cost[s] = 0;
	while (!q.empty()) {
		pair<int, int> p = q.top();
		q.pop();
		int c = p.first;
		int v = p.second;
		if (cost[v] < c)
			continue;
		for (vector<pair<int, int> >::const_iterator i = g[v].begin(); i != g[v].end(); ++i) {
			if (cost[i->first] > cost[v] + i->second) {
				cost[i->first] = cost[v] + i->second;
				q.push(make_pair(cost[i->first], i->first));
			}
		}
	}
	return cost;
}

int solve(int c, int n, int s, int d, const edges_t &edges)
{
	graph_t g;
	g.resize(n);
	for (auto i = edges.begin(); i != edges.end(); i++) {
		int a, b, f;
		tie(a, b, f) = *i;
		g[a].emplace_back(b, f);
		g[b].emplace_back(a, f);
	}

	vector<vector<int>> cost; // cost[?????????????????°][????????????]
	cost.resize(c+1);
	for (auto i = cost.begin(); i != cost.end(); ++i) {
		i->resize(n, INF);
	}
	cost[c] = dijkstra(n, g, s);
	for (int w = c-1; w >= 0; w--) {
		cost[w][s] = 0;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
		q.emplace(0, s);
		while (!q.empty()) {
			int e, v;
			tie(e, v) = q.top();
			q.pop();
			if (e > cost[w][v])
				continue;
			for (auto j = g[v].begin(); j != g[v].end(); ++j) {
				bool updated = false;
				if (cost[w][j->first] > e + j->second) {
					cost[w][j->first] = e + j->second;
					updated = true;
				}
				if (cost[w][j->first] > cost[w+1][v] + j->second/2) {
					cost[w][j->first] = cost[w+1][v] + j->second/2;
					updated = true;
				}
				if (updated) {
					q.emplace(cost[w][j->first], j->first);
				}
			}
		}
	}
	return cost[0][d];
}

void solve_stdio()
{
	while (true) {
		int c, n, m, s, d;
		if (!(cin >> c >> n >> m >> s >> d))
			break;
		if (c == 0)
			break;
		s--; d--;
		edges_t edges;
		for (int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			a--; b--;
			edges.emplace_back(a, b, f);
		}
		int ans = solve(c, n, s, d, edges);
		cout << ans << endl;
	}
}

int main()
{
	solve_stdio();
}

C++: //Solution for aoj:0212 Highway Express Bus
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
typedef pair<int, int>P;


struct S {
	int cost, to, num;
	S(int c, int t, int n) : cost(c), to(t), num(n){}
	bool operator>(const S &s) const {
		return cost > s.cost;
	}
};

const int INF = 1 << 30;
int c, n, m, s, d, ans;
int tocost[101][11];
vector<P> town[501];
priority_queue<S, vector<S>, greater<S> > pq;


void dijkstra(){
	while (!pq.empty()){
		S a = pq.top();
		pq.pop();
		for (int i = 0; i < town[a.to].size(); i++){
			int tt = town[a.to][i].first, cc = town[a.to][i].second;
			if (tocost[tt][a.num] > cc + a.cost){
				tocost[tt][a.num] = cc + a.cost;
				pq.push({ cc + a.cost, tt, a.num });
			}
			if (a.num>0&&tocost[tt][a.num-1] > cc/2 + a.cost){
				tocost[tt][a.num-1] = cc/2 + a.cost;
				pq.push({ cc/2 + a.cost, tt, a.num-1 });
			}
		}
	}
}
	int main(){
		while (cin >> c >> n >> m >> s >> d&&c){
			for (int i = 0; i < 101; i++)
				fill(tocost[i], tocost[i] + 11, INF);
			tocost[s][c] = 0;
			ans = INF;
			while (pq.size())
				pq.pop();
			for (int i = 0; i < n; i++)
					town[i].erase(town[i].begin(),town[i].end());
			for (int i = 0; i < m; i++){
				int a, b, c;
				cin >> a >> b >> c;
				town[a].push_back({ b, c });
				town[b].push_back({ a, c });
			}
			pq.push({ 0, s, c });
			dijkstra();
			for (int i = 0; i <= c; i++)
				ans = min(ans, tocost[d][i]);
			cout << ans << endl;
		}
		return 0;
	}

C++: #include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define MAX 100000
#define MAX_NODE_ID 100
#define MAX_TICKET 10
class Node{
public:
	int id;
	int cost;
	int ticket;
	Node(int i,int c,int t){
		id=i;
		cost=c;
		ticket=t;
	}
	bool operator < (const Node &o) const{
		return cost > o.cost;
	}
};
typedef priority_queue<Node> PQ;
int table[MAX_NODE_ID][MAX_NODE_ID];
bool visited[MAX_NODE_ID][MAX_TICKET];
int main(){

	for(int c,n,m,s,d;cin>>c>>n>>m>>s>>d&&(c||n||m||s||d);){
		for(int i=0;i<MAX_NODE_ID;i++)for(int j=0;j<MAX_NODE_ID;j++)table[i][j]=MAX;
		for(int i=0,a,b,f;i<m&&cin>>a>>b>>f;i++){
			table[a][b]=f;
			table[b][a]=f;
//			cout<<"table["<<a<<"]["<<b<<"]"<<table[a][b]<<endl;
//			cout<<"table["<<b<<"]["<<a<<"]"<<table[b][a]<<endl;
		}
		PQ pq;
		Node start(s,0,c);
		pq.push(start);
		while(!pq.empty()){
			int current_node=pq.top().id;
			int current_cost=pq.top().cost;
			int current_ticket=pq.top().ticket;
//			cout<<"current:"<<current_node<<endl;
			if(current_node==d)break;
			if(visited[current_node][current_ticket]);
			else{
				for(int i=1;i<=n;i++){
					if(current_node==i)continue;
					if(table[current_node][i]==MAX)continue;
	//				cout<<"["<<current_node<<"]["<<i<<"]"<<"cost:"<<table[current_node][i]<<endl;
					Node node1(i,current_cost+table[current_node][i],current_ticket);
					pq.push(node1);
					if(current_ticket>0){
						Node node2(i,current_cost+(table[current_node][i]/2),current_ticket-1);
						pq.push(node2);
					}
				}
			}
			pq.pop();
		}
		cout<<pq.top().cost<<endl;
	}


	return 0;
}