#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int>P;

int C[105][15];



int main(){
	
	int c,n,m,s,d;
	while(cin>>c>>n>>m>>s>>d,c){
		vector<P>V[105];
		
		for(int i=0;i<105;i++){
			for(int j=0;j<15;j++)C[i][j]=1145141919;
		}
		
		for(int i=0;i<m;i++){
			int x,y,z;
			cin>>x>>y>>z;
			V[x].push_back(P(y,z));
			V[y].push_back(P(x,z));
		}
		
		priority_queue<P , vector<P> , greater<P> >Q;
		
		Q.push(P(0,c*1000+s));
		
		while(!Q.empty()){
			int cost=Q.top().first;
			int pos=Q.top().second%1000;
			int card=Q.top().second/1000;
			Q.pop();
			
			if(pos==d){
				cout<<cost<<endl;
				break;
			}
			if(C[pos][card]!=1145141919){
				continue;
			}
			
			//cout<<"#"<<pos<<" "<<card<<" "<<cost<<endl;
			
			C[pos][card]=cost;
			for(int i=0;i<V[pos].size();i++){
				//cout<<"$$"<<V[pos][i].first<<" "<<V[pos][i].second<<endl;
				if(card>0){
					if(C[V[pos][i].first][card-1]==1145141919){
						Q.push(P(cost+V[pos][i].second/2,(card-1)*1000+V[pos][i].first));
					}
				}
				if(C[V[pos][i].first][card]==1145141919){
					Q.push(P(cost+V[pos][i].second,card*1000+V[pos][i].first));
				}
			}
			
		}
		
	}
	
	
	
	return 0;
}
