#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int, int>P;

struct node {
	int first, second, c;
};
bool operator<(node a, node b) {
	return a.second > b.second;
}
vector<P>E[100];
int d[100][11];

int main() {
	int c, n, m, s, g;
	while (scanf("%d%d%d%d%d", &c, &n, &m, &s, &g), c) {
		s--; g--;
		rep(i, 100)E[i].clear();
		memset(d, 0x3f, sizeof(d));
		rep(i, m) {
			int a, b, f; scanf("%d%d%d", &a, &b, &f);
			a--; b--;
			E[a].push_back(P(b, f)); E[b].push_back(P(a, f));
		}
		priority_queue<node>que;
		que.push({ s,0,c });
		d[s][0] = 0;
		while (!que.empty()) {
			node p = que.top(); que.pop();
			if (d[p.first][p.c - 1] < p.second)continue;
			for (P i : E[p.first]) {
				if (p.c&& d[i.first][p.c - 1] > p.second + i.second / 2) {
					d[i.first][p.c - 1] = p.second + i.second / 2;
					que.push({ i.first, d[i.first][p.c - 1],p.c - 1 });
				}
				if (d[i.first][p.c] > p.second + i.second) {
					d[i.first][p.c] = p.second + i.second;
					que.push({ i.first, d[i.first][p.c],p.c });
				}
			}
		}
		int Min = INT_MAX;
		rep(i, c + 1)Min = min(Min, d[g][i]);
		printf("%d\n", Min);
	}
}