#include <iostream>
#define INF 1000000000
using namespace std;


struct edge{
	int from, to, cost;
};

int ans[100000];
int counter=0;
bool flag=true;

void solve(){
	int d[101][11];//地点と割引回数
	edge route[500];//路線
	int c,n,m,s,t;//割引回数,町数,路線数,出発駅,到着駅
	cin >> c>>n>>m>>s>>t;
	if(c==0) {flag=false; return;}
	
	for(int i=0;i<m;i++){
		cin >>route[i].from>>route[i].to>>route[i].cost;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=0;j<c+1;j++){//割引回数は割引無しも必要
			d[i][j]=INF;
		}
	}
	
	d[s][0]=0;
	bool update=true;
	while(update){
		update=false;
		for(int i=0;i<m;i++){
			edge e=route[i];//見やすく
			for(int j=0;j<=c;j++){
				//まずは割引無し
				if(d[e.from][j]!=INF && d[e.to][j]>d[e.from][j]+e.cost){
					d[e.to][j]=d[e.from][j]+e.cost; update=true;
				}
				if(d[e.to][j]!=INF && d[e.from][j]>d[e.to][j]+e.cost){
					d[e.from][j]=d[e.to][j]+e.cost; update=true;
				}
				
			}
			
			for(int j=0;j<c;j++){
				if(d[e.from][j]!=INF && d[e.to][j+1]>d[e.from][j]+e.cost/2){
					d[e.to][j+1]=d[e.from][j]+e.cost/2; update=true;
				}
				if(d[e.to][j]!=INF && d[e.from][j+1]>d[e.to][j]+e.cost/2){
					d[e.from][j+1]=d[e.to][j]+e.cost/2; update=true;
				}
			}
		}
	}
	int k=INF;
	for(int i=0;i<=c;i++){
		if(k>d[t][i]) k=d[t][i];
	}
	ans[counter]=k;
	counter++;
}

int main(){
	while(flag){
		solve();
	}
	for(int i=0;i<counter;i++){
		cout << ans[i]<<endl;
	}
}
	
	