#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define INF 99999999
typedef pair<int, int> P;
typedef pair<P, int> PP;
struct Edge
{
	int to;
	int cost;
};

void solve()
{
	int c, n, m, s, d;
	while(cin >> c >> n >> m >> s >> d, c || n || m || m || s)
	{
		vector<Edge> V[101];
		for(int i = 0; i < m; ++i)
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			--from; --to;
			Edge e1 = {to, cost};
			Edge e2 = {from, cost};
			V[from].push_back(e1);
			V[to].push_back(e2);
		}
		vector< vector<int> > dist(n, vector<int>(c + 1));
		for(int i = 0; i < dist.size(); ++i)
		{
			for(int j = 0; j < dist[i].size(); ++j)
			{
				dist[i][j] = INF;
			}
		}
		priority_queue<PP, vector<PP>, greater<PP> > pq;
		--s;
		dist[s][0] = 0;
		pq.push(PP(P(0, s), 0));
		while(!pq.empty())
		{
			PP pp = pq.top();
			pq.pop();
			int v = pp.first.second;
			int ticket = pp.second;
			if(dist[v][ticket] < pp.first.first)
			{
				continue;
			}
			for(int i = 0; i < V[v].size(); ++i)
			{
				Edge e = V[v][i];
				if(dist[e.to][ticket] > pp.first.first + e.cost)
				{
					dist[e.to][ticket] = pp.first.first + e.cost;
					pq.push(PP(P(dist[e.to][ticket], e.to), ticket));
				}
				if(ticket < c && dist[e.to][ticket + 1] > pp.first.first + e.cost / 2)
				{
					dist[e.to][ticket + 1] = pp.first.first + e.cost / 2;
					pq.push(PP(P(dist[e.to][ticket + 1], e.to), ticket + 1));
				}
			}
		}
		int min_cost = INF;
		for(int i = 0; i <= c; ++i)
		{
			if(min_cost > dist[d - 1][i])
			{
				min_cost = dist[d - 1][i];
			}
		}
		cout << min_cost << endl;
	}
}

int main()
{
	solve();
	return(0);
}