#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const int INF = 1 << 25;
int dist[100][11];

struct State {
	int v, c, d;
	bool operator <(const State& x) const {
		return d > x.d;
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int c, n, m, s, g;
	while(cin >> c >> n >> m >> s >> g, n) {
		s--, g--;

		vector<P> G[100];
		for(int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			a--, b--;
			G[a].push_back({ b, f });
			G[b].push_back({ a, f });
		}

		fill((int*)begin(dist), (int*)end(dist), INF);
		dist[s][c] = 0;
		priority_queue<State> q;
		q.push({ s, c, 0 });
		while(q.size()) {
			int v = q.top().v, rem = q.top().c, d = q.top().d;
			q.pop();
			if(dist[v][c] < d) continue;
			for(auto e : G[v]) {
				int cost[2] = { e.second, e.second / 2 };
				for(int i = 0; i < 2; i++) {
					int u = e.first;
					if(rem == 0 && i == 1) continue;
					if(dist[u][rem - i] > d + cost[i]) {
						dist[u][rem - i] = d + cost[i];
						q.push({ u, rem - i, d + cost[i] });
					}
				}
			}
		}

		int ans = 1e9;
		for(int i = 0; i <= c; i++) {
			ans = min(ans, dist[g][i]);
		}

		cout << ans << endl;
	}
}