//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 << 29;
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&&n&&m&&s){
			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].clear();
			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;
	}