#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int c, n, m, s, d, a, b, f, dp[11][100]; vector<pair<int, int> > G[100];
int main() {
	while(scanf("%d%d%d%d%d", &c, &n, &m, &s, &d), s--, d--, c) {
		for(int i = 0; i < n; i++) G[i].clear();
		for(int i = 0; i <= c; i++) {
			for(int j = 0; j < n; j++) dp[i][j] = 1000000000;
		}
		dp[0][s] = 0;
		for(int i = 0; i < m; i++) {
			scanf("%d%d%d", &a, &b, &f);
			G[a - 1].push_back(make_pair(b - 1, f));
			G[b - 1].push_back(make_pair(a - 1, f));
		}
		priority_queue<vector<int> > que; que.push({0, s, 0});
		while(!que.empty()) {
			vector<int> v1 = que.top(); que.pop();
			for(int i = 0; i < G[v1[1]].size(); i++) {
				int u = G[v1[1]][i].first, w = G[v1[1]][i].second;
				if(dp[v1[2]][u] > dp[v1[2]][v1[1]] + w) {
					dp[v1[2]][u] = dp[v1[2]][v1[1]] + w;
					que.push({-dp[v1[2]][u], u, v1[2]});
				}
				if(v1[2] < c && dp[v1[2] + 1][u] > dp[v1[2]][v1[1]] + w / 2) {
					dp[v1[2] + 1][u] = dp[v1[2]][v1[1]] + w / 2;
					que.push({-dp[v1[2] + 1][u], u, v1[2] + 1});
				}
			}
		}
		int ret = 1000000000;
		for(int i = 0; i <= c; i++) ret = min(ret, dp[i][d]);
		printf("%d\n", ret);
	}
}