#include <iostream>
#include <map>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

class Vertax
{
public:
	int n, d, c;
	Vertax(){}
	Vertax(int n, int d, int c) : n(n), d(d), c(c){}
};
bool operator > (Vertax v1, Vertax v2)
{
	if (v1.c == v2.c) return v1.d > v2.d;
	return v1.c > v2.c;
}
bool operator < (Vertax v1, Vertax v2)
{
	if (v1.c == v2.c) return v1.d < v2.d;
	return v1.c < v2.c;
}

typedef pair<int, int> p;
const int INF = 99999999;

int C, N, M, S, D; //??????????????°???????????°???????????°???????????°???????????°

int main()
{
	while (cin >> C >> N >> M >> S >> D, C + N + M + S + D)
	{
		vector<p> edge[101];
		priority_queue<Vertax, vector<Vertax>, greater<Vertax>> que;
		int distance[11][101];

		for (int i = 0; i < M; i++)
		{
			int a, b, f;
			cin >> a >> b >> f;
			edge[a].push_back(p(b, f));
			edge[b].push_back(p(a, f));
		}
		for (int i = 0; i <= C; i++)
		{
			for (int j = 0; j <= N; j++)
			{
				distance[i][j] = INF;
			}
		}
		
		Vertax start;
		start.n = S;
		start.d = 0;
		start.c = 0;
		que.push(start);
		distance[0][S] = 0;

		while (!que.empty())
		{
			int n = que.top().n;
			int d = que.top().d;
			int c = que.top().c;
			que.pop();

			for (int i = 0; i < edge[n].size(); i++)
			{
				int to = edge[n][i].first;
				int dis = edge[n][i].second;

				if (distance[c][to] > d + dis)
				{
					distance[c][to] = d + dis;
					que.push(Vertax(to, d + dis, c));
				}
				if (c < C && distance[c + 1][to] > d + (dis / 2))
				{
					distance[c + 1][to] = d + (dis / 2);
					que.push(Vertax(to, d + (dis / 2), c + 1));
				}
			}
		}

		int ans = INF;
		for (int i = 0; i <= C; i++)
		{
			ans = min(ans, distance[i][D]);
		}
		cout << ans << endl;
	}

	return 0;
}