#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;
const int INF = 1<<25;
int main(){
	int c, n, m, s, d, a, b, f;
	
	while(cin >> c >> n >> m >> s >> d && (c || m || n || s || d)) {
		s--, d--;
		int cost[110][110] = {}, ret[11][110];
		rep(i,m) {
			cin >> a >> b >> f;
			a--, b--;
			cost[a][b] = cost[b][a] = f;
		}
		rep(i,c+1) {
			rep(j,n) { 
				ret[i][j] = INF;
			}
		}
		queue<pair<int, int> > q;
		q.push(make_pair(c,s));
		ret[c][s] = 0;
		while(!q.empty()) {
			int node = q.front().second, nc = q.front().first; q.pop();
			rep(i,n) {
				if(cost[node][i]) {
					if(ret[nc][i] > ret[nc][node] + cost[node][i]) {
						ret[nc][i] = ret[nc][node] + cost[node][i];
						q.push(make_pair(nc, i));
					}
					if(nc>0 && ret[nc - 1][i] > ret[nc][node] + cost[node][i] / 2) {
						 ret[nc - 1][i] = ret[nc][node] + cost[node][i] / 2;
						 q.push(make_pair(nc-1, i));
					}
				}
			}	
		}
		int res = INF;
		rep(i,c+1) {
			res = min(res,ret[i][d]);
		}
		cout << res << endl;
	}
}