#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <tuple>
#include <queue>

using namespace std;

#define int long long

class Solver {
};

signed main() {
	while (true) {
		int c, n, m, s, d;
		cin >> c >> n >> m >> s >> d;
		s--;
		d--;
		if (c == 0)break;

		vector<vector<vector<tuple<int, int, int>>>> graph(c + 1,
			vector<vector<tuple<int, int, int>>>(n));

		for (int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			a--;
			b--;
			for (int i = 0; i <= c; i++) {
				graph[i][a].emplace_back(make_tuple(i, b, f));
				graph[i][b].emplace_back(make_tuple(i, a, f));
				if (i < c) {
					graph[i][a].emplace_back(make_tuple(i + 1, b, f/2));
					graph[i][b].emplace_back(make_tuple(i + 1, a, f/2));
				}
			}
		}

		priority_queue<tuple<int, int, int>> que;
		vector<vector<int>> dist(c + 1, vector<int>(n, 1e9));
		que.emplace(make_tuple(0, s, 0));
		while (que.size() > 0) {
			int cnt = get<0>(que.top());
			int pos = get<1>(que.top());
			int distance = get<2>(que.top());
			que.pop();
			if (dist[cnt][pos] <= distance)continue;

			dist[cnt][pos] = distance;
			for (int i = 0; i < graph[cnt][pos].size(); i++) {
				int cnt_t = get<0>(graph[cnt][pos][i]);
				int pos_t = get<1>(graph[cnt][pos][i]);
				int distance_t = get<2>(graph[cnt][pos][i]);
				distance_t += distance;

				if (dist[cnt_t][pos_t] <= distance_t)continue;

				que.emplace(make_tuple(cnt_t, pos_t, distance_t));
			}
		}

		int res = 1e9;
		for (int i = 0; i <= c; i++)res = min(res, dist[i][d]);
		cout << res << endl;
	}
}
