#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int c,n,m,s,d;
const int INF = 2*1e9;
vector<pair<int,int>> G[100];
ll D[100][10];

struct P
{
	int time,v,chk;
	P(int time,int v,int chk)
	{
		this->time=time;
		this->v = v;
		this->chk = chk;
	}
};

bool operator<(P a,P b)
{
	return a.time>b.time;
}

void dijkstra(int chiket)
{
	for(int i = 0;i<100;i++)
	{
		for(int j = 0;j<10;j++)
		{
			D[i][j]=INF;
		}
	}
	D[s][chiket]=0;
	priority_queue<P> PQ;
	PQ.emplace(0,s,chiket);
	while(!PQ.empty())
	{
		//cout<<PQ.size()<<endl;
		auto now = PQ.top();
		PQ.pop();
		//cout<<now.time<<endl;
		if(D[now.v][now.chk]!=now.time)continue;
		for(auto next:G[now.v])
		{
			if(D[next.first][now.chk]>now.time+next.second)
			{
				D[next.first][now.chk]=now.time+next.second;
				PQ.emplace(D[next.first][now.chk],next.first,now.chk);
			}
			if(now.chk<1)continue;
			if(D[next.first][now.chk-1]>now.time+next.second/2)
			{
				D[next.first][now.chk-1] = now.time+next.second/2;
				PQ.emplace(D[next.first][now.chk-1],next.first,now.chk-1);
			}
		}
	}
	ll mn = INF;
	for(int i = 0;i<10;i++)
	{
		mn = min(mn,D[d][i]);
	}
	cout<<mn<<endl;
}

int main()
{
	while(1)
	{
		cin >> c >> n >> m >> s >> d;
		if(c==0)break;
		for(int i = 0;i<n;i++)
		{
			G[i].clear();
		}
		s--;
		d--;
		for(int i = 0;i<m;i++)
		{
			int a,b,f;
			cin >> a >> b >> f;
			a--;
			b--;
			G[a].emplace_back(b,f);
			G[b].emplace_back(a,f);
		}
		dijkstra(c);
	}
}
