#include<bits/stdc++.h>

using namespace std;

const int INF = 1e7;
int Cost[101][101], DpMoney[11][101];
bool Used[11][101];


void solve(int ticket, int n, int start) {
	int u, v;

	for (int i = 0; i < 11; ++i) {
		fill(DpMoney[i], DpMoney[i] + 101, INF);
		fill(Used[i], Used[i] + 101, false);
	}

	DpMoney[0][start] = 0;
	while (true) {
		u = -1;
		for (int i = 0; i <= ticket; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (!Used[i][j] && (u == -1 || DpMoney[i][j] < DpMoney[u][v])) {
					u = i;
					v = j;
				}
			}
		}
		if (u == -1) {
			break;
		}
		Used[u][v] = true;

		for (int k = 1; k <= n; ++k) {
			DpMoney[u][k] = min(DpMoney[u][k], DpMoney[u][v] + Cost[v][k]);
			if (u + 1 <= ticket) {
				DpMoney[u + 1][k] = min(DpMoney[u + 1][k], DpMoney[u][v] + Cost[v][k] / 2);
			}
		}
	}
	
}

int main() {
	int c, n, m, s, d, a, b, f;

	while (cin >> c >> n >> m >> s >> d, c) {
		for (int i = 0; i < 101; ++i) {
			fill(Cost[i], Cost[i] + 101, INF);
		}
		for (int i = 0; i < m; ++i) {
			cin >> a >> b >> f;
			Cost[a][b] = f;
			Cost[b][a] = f;
		}
		solve(c, n, s);
		f = INF;
		for (int i = 0; i <= c; ++i) {
			f = min(f, DpMoney[i][d]);
		}
		cout << f << endl;
	}

	return 0;
}
