#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9
typedef pair<mp,ll> mmp;

int main(){
    while(1){
	ll c,n,m,s,d;
	cin>>c>>n>>m>>s>>d;
	if(c==0)break;
	s--,d--;
	vector<vector<mp> > g(n);
	for(ll i=0;i<m;i++){
		ll a,b,f;
		cin>>a>>b>>f;
		a--;
		b--;
		g[a].push_back(mp(f,b) );
		g[b].push_back(mp(f,a) );
	}
	priority_queue<mmp,vector<mmp>,greater<mmp> > q;
	q.push(mmp(mp(0,0),s) );
	vector<vector<bool> > used(n,vector<bool>(c+1,false) );
	while(!q.empty() ){
		mmp now = q.top();
		q.pop();
		ll ncost = now.first.first;
		ll cc = now.first.second;
		ll nn = now.second;
		//cout<<nn<<' '<<cc<<endl;
		if(nn==d){
		    	//cout<<"ok"<<endl;
			cout<<ncost<<endl;
			break;
		}
		if(used[nn][cc]) continue;
		used[nn][cc] = true;
		for(ll i=0;i<g[nn].size();i++){
			ll next = g[nn][i].second;
			ll nec = g[nn][i].first;
			if(used[next][cc])continue;
			q.push(mmp(mp(ncost+nec,cc),next) );
			if(cc < c){
			    if(used[next][cc+1])continue;
				q.push(mmp(mp(ncost+nec/2,cc+1),next) );
			}
		}
	}


    }
	return 0;
}

