#include<bits/stdc++.h>
using namespace std;

class Node{
public:
	int num;
	int c;
	int fee;

	Node(){ num = 0; c = 0; fee = 0;}
	Node(int num, int c, int fee) : num(num), c(c), fee(fee){}

};

bool operator< (const Node &n1, const Node &n2){
	return n1.fee < n2.fee;
}

bool operator>(const Node &n1, const Node &n2){
	return n1.fee > n2.fee;
}

int main(void){

	int c, n, m, s, d;
	while (cin >> c >> n >> m >> s >> d, c, n, m, s, d){
		vector<vector <int> > path(n + 1);
		vector<vector <int> > cost(n + 1);
		bool checked[101][11] = { false };

		for (int i = 0; i < m; i++){
			int a, b, f;
			cin >> a >> b >> f;
			path[a].push_back(b);
			cost[a].push_back(f);
			path[b].push_back(a);
			cost[b].push_back(f);
		}

		priority_queue<Node, vector<Node>, greater<vector<Node>::value_type> > que;

		que.push(Node(s, c, 0));

		while (!que.empty()){
			Node buff = que.top();
			que.pop();
			if (checked[buff.num][buff.c]) continue;
			checked[buff.num][buff.c] = true;
			if (buff.num == d){
				cout << buff.fee << endl;
				break;
			}

			int nnum = buff.num;
			for (int i = 0; i < path[nnum].size(); i++){
				que.push(Node(path[nnum][i], buff.c, buff.fee + cost[nnum][i]));
				if (buff.c > 0) que.push(Node(path[nnum][i], buff.c - 1, buff.fee + cost[nnum][i] / 2));
			}
		}
	}
	return 0;
}