#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <map>

static const int INF = 1 << 20;

using namespace std;

struct state
{
	int ticket, id, cost;
};

struct comparator : public binary_function<state, state, bool>
{
	bool operator() (const state &x, const state &y) const { return x.cost > y.cost; }
};

static bool det[11][101];
static int edges[101][101];

int main()
{
	int C,N,M,S,D;
	while(cin>>C>>N>>M>>S>>D,C|N|S|M|D)
	{
		for (int c = 0; c <= C; c++)
			for (int i = 1; i <= N; i++)
				det[c][i] = false;

		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				edges[i][j] = INF;

		for (int i = 0; i < M; i++)
		{
			int a,b,f;
			cin>>a>>b>>f;
			edges[a][b] = edges[b][a] = f;
		}

		state init = { C, S, 0 };

		// Dijkstra
		priority_queue<state, vector<state>, comparator> Q;
		Q.push(init);

		int min_cost = INF;
		while (!Q.empty())
		{
			state s = Q.top();
			Q.pop();
			if (det[s.ticket][s.id]) continue;
			det[s.ticket][s.id] = true;

			if (s.id == D) min_cost = min(min_cost, s.cost);

			for (int i = 1; i <= N; i++)
			{
				if (edges[s.id][i] == INF) continue;

				int cost = s.cost + edges[s.id][i];
				state s2 = { s.ticket, i, cost };

				if (!det[s2.ticket][s2.id]) Q.push(s2);

				if (s.ticket > 0)
				{
					cost = s.cost + edges[s.id][i] / 2;
					state s3 = { s.ticket - 1, i, cost };
					if (!det[s3.ticket][s3.id]) Q.push(s3);
				}
			}
		}
		cout << min_cost << endl;
	}
	return 0;
}