#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>

#define rep(i,n)	for(int i = 0;i < n;i++)
#define rep2(i,n)	for(int i = 1;i <= n;i++)
#define each(i,x)	for(auto & i : x)

struct edge
{
	edge(int _s,int _t,int _cost)
	{
		s = _s;t = _t;cost = _cost;
	}
	int s;
	int t;
	int cost;
};

using namespace std;

int main()
{
	int c,n,m,s,d;
	cin >> c >> n >> m >> s >> d;
	while(c || n || m || s || d)
	{
		s--;d--;
		vector<list<edge>> town(n);
		vector<edge> eary;
		rep(i,m)
		{
			int a,b,f;
			cin >> a >> b >> f;
			a--;b--;
			town[a].push_back(edge(a,b,f));
			town[b].push_back(edge(b,a,f));
			eary.push_back(edge(a,b,f));
		}
		vector<vector<int>> cost(c+1,vector<int>(n,2000000));
		cost[0][s] = 0;
		bool flg;
		do
		{
			flg = false;
			each(e,eary)
			{
				rep(i,c+1)
				{
					if(cost[i][e.s] > cost[i][e.t] + e.cost)
					{
						cost[i][e.s] = cost[i][e.t] + e.cost;
						flg = true;
					}
					else if(cost[i][e.t] > cost[i][e.s] + e.cost)
					{
						cost[i][e.t] = cost[i][e.s] + e.cost;
						flg = true;
					}
				}
				rep(i,c)
				{
					if(cost[i+1][e.s] > cost[i][e.t] + e.cost/2)
					{
						cost[i+1][e.s] = cost[i][e.t] + e.cost/2;
						flg = true;
					}
					if(cost[i+1][e.t] > cost[i][e.s] + e.cost/2)
					{
						cost[i+1][e.t] = cost[i][e.s] + e.cost/2;
						flg = true;
					}
				}
			}
		}while(flg);
		int min = 10000000;
		rep(i,c+1)
		{
			if(cost[i][d] < min)
			{
				min = cost[i][d];
			}
		}
		cout << min << endl;
		cin >> c >> n >> m >> s >> d;
	}
	return 0;
}