//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, jud;
	S(int c, int t, int n, int j) : cost(c), to(t), num(n), jud(j) {}
	bool operator>(const S &s) const {
		return cost > s.cost;
	}
};

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

void pq_set(int p, int sum, int j){
	for (int i = 0; i < town[p].size(); i++){
			pq.push(S(town[p][i].second + sum, town[p][i].first, j, 0));
			if (j)
				pq.push(S(town[p][i].second / 2 + sum, town[p][i].first, j - 1, 1));
	}
}

void dijkstra(){
	while (!pq.empty()){
		S a = pq.top();
		pq.pop();
		if (a.jud){
			if (tocost[a.to][a.num] < a.cost&&a.to!=s){
				tocost[a.to][a.num] = a.cost;
					pq_set(a.to, tocost[a.to][a.num], a.num);

			}
		}
			else{
				if (tocost[a.to][a.num] < a.cost&&a.to!=s){
					tocost[a.to][a.num] = a.cost;
					pq_set(a.to, tocost[a.to][a.num], a.num);
					
				}
			}
	}
}
	int main(){
		while (cin >> c >> n >> m >> s >> d&&c){
			for (int i = 0; i < 101; i++)
				fill(tocost[i], tocost[i] + 11, INF);
			fill(tocost[s], tocost[s] + 11, 0);
			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*-1 });
				town[b].push_back({ a, c*-1 });
			}
			pq_set(s, 0, c);
			dijkstra();
			cout << -tocost[d][0] << endl;
		}
	}