#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)
#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
#define sinttt(i,j,k) scanf("%d%d%d",&i,&j,&k);
#define sintttt(i,j,k,m) scanf("%d%d%d%d",&i,&j,&k,&m);

#define INF 1010000000
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

class S{
	public:
	int p,n,t;
	S(int p,int n,int t):p(p),n(n),t(t){}
	
	bool operator<(const S& a)const{
		return n>a.n;
	}
};


int main(){
	while(1){
		int c,n,m,s,g;
		cin>>c>>n>>m>>s>>g;
		if(n==0)break;
		vector<pair<int,int> > load[101];
		rep(i,m){
			int a,b,c;
			cin>>a>>b>>c;
			load[a].push_back(make_pair(b,c));
			load[b].push_back(make_pair(a,c));
		}
		
		priority_queue<S> que;
		que.push(S(s,0,0));
		int visit[11][101];
		int ans=-1;
		
		rep(j,11)rep(i,101)visit[j][i]=0;
		
		while(1){
			if(que.empty()==1){
				break;
			}
			
			S u=que.top();
			que.pop();
			
			if(visit[u.t][u.p]==1){
				continue;
			}
			visit[u.t][u.p]=1;
			
			if(u.p==g){
				ans=u.n;
				break;
			}
			
			rep(i,load[u.p].size()){
				if(u.t<c){
					que.push( S( load[u.p][i].first,  u.n+load[u.p][i].second/2 ,u.t+1));
				}
				que.push( S( load[u.p][i].first,  u.n+load[u.p][i].second,u.t));
			}
		}
		printf("%d\n",ans);
	}
}