#include<iostream>
#include<utility>
#include<vector>
#include<cstdio>
#include<queue>
#include <map>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
//int in(){int x;cin>>x;return x;}

int main ()
{
	int c,n,m,s,d;
	while(cin>>c>>n>>m>>s>>d&&c&&n&&m&&s&&d)
	{
		int flg[110]={};
		int ans =0;
		priority_queue < PP, vector<PP>, greater<PP> > q;
		vector< pair< int,int > > way[110];
		for(int i=0;i<m;i++)
		{
			int a,b,f;
			cin>>a>>b>>f;
			way[a].push_back(pair<int,int>(b,f));
			way[b].push_back(pair<int,int>(a,f));
		}
		pair< int , pair<int,int> > next;
		next.first=0;next.second.first=s;next.second.second=c;
		q.push(next);
		while(!q.empty())
		{
			pair< int , pair<int,int> > now=q.top();q.pop();
			flg[now.second.first]=1;
			if(now.second.first==d)
			{
				ans=now.first;
				break;
			}
			
			for(int i=0;i<way[now.second.first].size();i++)
			{
				if(flg[way[now.second.first][i].first]==1)continue;
				next.first=now.first+way[now.second.first][i].second;
				next.second.first=way[now.second.first][i].first;
				q.push(next);
				next.first=now.first+way[now.second.first][i].second/2;
				next.second.first=way[now.second.first][i].first;
				next.second.second=now.second.second-1;
				q.push(next);
			}
			
		}
		cout<<ans<<endl;
	}
	
	
	return 0;
}