#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>

using namespace std;
typedef pair<int, int> Pi;
typedef pair<int, Pi> Ti;

int c, n, m, s, d;
vector<vector<Pi>> edge;

int djk(int s, int g) {
	int d[100 + 16][11];
	for (int i = 0; i < n; i++)for (int j = 0; j <= c; j++)d[i][j] = 1000000000;
	d[s][c] = 0;
	priority_queue<Ti, vector<Ti>, greater<Ti>> pq;
	pq.push(make_pair(0, make_pair(s, c)));
	while (pq.size()) {
		Ti tmp = pq.top(); pq.pop();
		int N = tmp.second.first, ticket = tmp.second.second;
		if (d[N][ticket] < tmp.first)continue;
		for (int i = 0; i < edge[N].size(); i++) {
			int to = edge[N][i].first, cost = edge[N][i].second;
			if (ticket > 0) {
				if (d[to][ticket - 1] > d[N][ticket] + cost / 2) {
					d[to][ticket - 1] = d[N][ticket] + cost / 2;
					pq.push(make_pair(d[to][ticket - 1], make_pair(to, ticket - 1)));
				}
			}
			if (d[to][ticket] > d[N][ticket] + cost) {
				d[to][ticket] = d[N][ticket] + cost;
				pq.push(make_pair(d[to][ticket], make_pair(to, ticket)));
			}
		}
	}
	int ans = 1000000000;
	for (int i = 0; i <= c; i++)ans = min(ans, d[g][i]);
	return ans;
}

int main() {
	while (cin >> c >> n >> m >> s >> d, c + n + m + s + d) {
		s--, d--;
		edge.resize(n);

		for (int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f, a--, b--;
			edge[a].push_back(make_pair(b, f));
			edge[b].push_back(make_pair(a, f));
		}
		cout << djk(s, d) << endl;
		edge.clear();
	}
	return 0;
}