#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define INF 100000000

typedef pair<int, int> P;

int main() {
	int c, n, m, s, d;
	while (cin >> c >> n >> m >> s >> d) {
		if (c == 0 && n == 0 && m == 0 && s == 0 && d == 0) {
			break;
		}
		vector< vector<int> > ff(n+1, vector<int>(n+1, INF));
		vector< vector<int> > ddd(101, vector<int>(101, INF));
		int a, b, f;
		for (int i = 0; i < m; i++) {
			cin >> a >> b >> f;
			ff[a][b] = ff[b][a] = f;
			ddd[a][b] = ddd[b][a] = f;
		}
		for (int i = 1; i <= n; i++) {
			ddd[i][i] = 0;
		}
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					ddd[i][j] = min(ddd[i][j], ddd[i][k]+ddd[k][j]);
				}
			}
		}
		vector< vector< vector<int> > > dp(101, vector< vector<int> >(101, vector<int>(11, INF)));
		for (int i = 1; i < 101; i++) {
			dp[i][i][0] = 0;
			dp[s][i][0] = ddd[s][i];
			dp[i][d][0] = ddd[i][d];
		}
		/*for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cout << ddd[i][j] << ' ';
			}
			cout << endl;
		}
		cout << endl;*/
		set<P> st[101][101][11];
		for (int k = 1; k <= c; k++) {
			for (int i = 1; i <= n; i++) {
				dp[s][i][k] = dp[s][i][k-1];
				dp[i][d][k] = dp[i][d][k-1];
				st[s][i][k] = st[s][i][k-1];
				st[i][d][k] = st[i][d][k-1];
				int ka, kb, kc, kd;
				ka = kb = kc = kd = 0;
				for (int j = 1; j <= n; j++) {
					for (int p = 1; p <= n; p++) {
						if (ff[j][p] != INF && st[s][i][k].find(P(j, p)) == st[s][i][k].end()) { //dd[s][i][k][j][p]
							if (dp[s][i][k] > dp[s][j][k-1]+(ff[j][p]/2)+ddd[p][i]) {
								dp[s][i][k] = dp[s][j][k-1]+(ff[j][p]/2)+ddd[p][i];
								ka = j;
								kb = p;
							}
						}
						if (ff[j][p] != INF && st[i][d][k].find(P(j, p)) == st[i][d][k].end()) { //dd[i][D][k][j][p]
							if (dp[i][d][k] > dp[i][j][k-1]+(ff[j][p]/2)+ddd[p][d]) {
								dp[i][d][k] = dp[i][j][k-1]+(ff[j][p]/2)+ddd[p][d];
								kc = j;
								kc = p;
							}
						}
					}
				}
				st[s][i][k].insert(P(ka, kb));
				st[i][d][k].insert(P(kc, kd));
				//dd[s][i][k][a][b] = dd[i][D][k][C][dk] = 1;
			}
			/*for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					cout << dp[i][j][k] << ' ';
				}
				cout << endl;
			}
			cout << endl;*/
		}
		cout << dp[s][d][c] << endl;
	}
	return 0;
}