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

#define INF 100000000
typedef pair<int, int> P;
typedef pair<int, P> P2;

int main(){
	while(true){
	int c, n, m, s, d;
	vector<P>es[105];
	cin >> c >> n >> m >> s >> d;
	if(n == 0) return 0;
	int dp[105][15] = {0};
	for(int i = 0; i < 105; i++){
		for(int j = 0; j < 15; j++){
			dp[i][j] = INF;
		}
	}
	s--; d--;
	dp[s][0] = 0;
	for(int i = 0; i < m; i++){
		int a, b, f;
		cin >> a >> b >> f;
		a--; b--;
		es[a].push_back(P(b, f));
		es[b].push_back(P(a, f));
	}
	int res = INF;
	queue<P2>que;
	que.push(P2(0, P(s, 0)));
	while(!que.empty()){
		P2 p2 = que.front();
		que.pop();
		int v = p2.second.first;
		int nowc = p2.first;
		int nowchi = p2.second.second;
		if(v == d){
			res = min(res, nowc);
			continue;
		}
		for(int u = 0; u < es[v].size(); u++){
			int to = es[v][u].first;
			int cost = es[v][u].second;
			if(dp[to][nowchi] > nowc + cost){
				dp[to][nowchi] = nowc + cost;
				//cout << to << endl;
				que.push(P2(dp[to][nowchi], P(to, nowchi)));
			}
			if(nowchi + 1 <= c){
				if(dp[to][nowchi + 1] > nowc + (cost / 2)){
					dp[to][nowchi + 1] = nowc + (cost / 2);
					que.push(P2(dp[to][nowchi + 1], P(to, nowchi + 1)));
				}
			}
		}
	}
	cout << res << endl;
}
}

