#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

#define MAX_N 101
#define MAX_C 11

#define WHITE 0
#define GRAY 1
#define BLACK 2

typedef pair<int, int> pii;

struct edge { int to, c; };

vector<edge> G[MAX_N];
int color[MAX_N];
int	minc[MAX_C][MAX_N]; //dp?????????????????° ????????????id

void dijkstra(int C, int s) {
	priority_queue<pii, vector<pii>, greater<pii> >PQ; //minc v

	memset(color, WHITE, sizeof(color));
	fill(minc[C], minc[C + 1], INF);

	//?§????
	PQ.push(pii(0, s));
	minc[C][s] = 0;
	color[s] = GRAY;

	//PQ???????´????????????°
	while (!PQ.empty()) {
		//minc???????°??????¨??????????´????????????????
		pii p = PQ.top(); PQ.pop();

		int u = p.second;
		color[u] = BLACK;
		//????????§???????????°??????
		if (minc[C][u] < p.first) continue;

		//??£??\????????????????????¨????????????
		for (int j = 0; j < G[u].size(); j++) {
			edge e = G[u][j];
			if (color[e.to] == BLACK)continue;
			int m = (C == 0 ? minc[C][u] + e.c : min(minc[C][u] + e.c, minc[C - 1][u] + e.c / 2));
			if (minc[C][e.to] > m) {
				minc[C][e.to] = m;
				PQ.push(pii(minc[C][e.to], e.to));
				color[e.to] = GRAY;
			}
		}
	}
}

int main() {
	for (int C, n, m, s, d; cin >> C >> n >> m >> s >> d&&C;) {
		for (int i = 0; i < m; i++) {
			int a, b, f; scanf("%d%d%d", &a, &b, &f);
			edge e; e.to = b; e.c = f;
			G[a].push_back(e);
			e.to = a; e.c = f;
			G[b].push_back(e);
		}
		for (int i = 0; i <= C; i++) {
			dijkstra(i, s);
		}

		cout << minc[C][d] << endl;

		for (int i = 0; i <= n; i++) {
			G[i].clear();
		}
	}
	return 0;
}