#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<pair<int,int>,int> NODE;
#define cost first.first
#define ticket first.second
#define city second
#define make_bus_st(a,b,c) make_pair(make_pair(a,b),c)

int busMap[200][200] ;
int memo[200][20];

int main()
{
	int C, N, M, S, D;
	int a, b, f;
	
	while(cin >> C >> N >> M >> S >> D, C, N, M, S, D) {
		for(int i = 0; i < 200; i++) {
			for(int j = 0; j < 200; j++) {
				busMap[i][j] = 0;
				if(j < 20) { memo[i][j] = (1<<21); }
			}
		}
		
		vector<int> nextCity[200];
		
		for(int i = 0; i < M; i++) {
			cin >> a >> b >> f;
			busMap[a][b] = busMap[b][a] = f;
			nextCity[a].push_back(b);
			nextCity[b].push_back(a);
		}
		
		priority_queue<NODE> bus;
		bus.push(make_bus_st(0,C,S));
		
		while(!bus.empty()) {
			NODE tmp = bus.top();
			bus.pop();
			
			for(int i = 0; i < nextCity[tmp.city].size(); i++) {
				int next = nextCity[tmp.city][i];
				
				if((busMap[tmp.city][next] + tmp.cost) < memo[next][tmp.ticket]) {
					memo[next][tmp.ticket] = busMap[tmp.city][next] + tmp.cost;
					bus.push(make_bus_st(memo[next][tmp.ticket], tmp.ticket, next));
				}
				if(tmp.ticket && (((busMap[tmp.city][next] / 2) + tmp.cost) < memo[next][tmp.ticket-1])) {
					memo[next][tmp.ticket-1] = (busMap[tmp.city][next] / 2) + tmp.cost;
					bus.push(make_bus_st(memo[next][tmp.ticket-1], tmp.ticket-1, next));
				}
			}
		}
		
		int ans = (1<<21);
		for(int i = 0; i <= C; i++) {
			ans = min(ans, memo[D][i]);
		}
		cout << ans << endl;
	}
	
	
	return 0;
}