#include<stdio.h>
#define INF 10000000
int c,n,m,s,g;
int e[100][100];
int d[11][100];
int i,j;
bool used[11][100];

int min(int a,int b){return a<b?a:b;}

int main(){
	while(1){
		scanf("%d %d %d %d %d",&c,&n,&m,&s,&g);
		if(c==0)return 0;
		for(i=0;i<n;i++)for(j=0;j<n;j++)e[j][i]=INF;
		for(i=0;i<m;i++){
			int a,b,f;
			scanf("%d %d %d",&a,&b,&f);
			e[a-1][b-1]=f;
			e[b-1][a-1]=f;
		}
		for(i=0;i<n;i++)for(j=0;j<=c;j++){
			d[j][i]=INF;
			used[j][i]=false;
		}
		d[c][s-1]=0;
		while(1){
			int nei=-1;
			int nej;
			for(i=0;i<n;i++)for(j=0;j<=c;j++){
				if(!used[j][i]&&(nei==-1||d[j][i]<d[nej][nei])){
					nei=i;
					nej=j;
				}
			}
			if(nei==-1)break;
			used[nej][nei]=true;
			for(i=0;i<n;i++){
				d[nej][i]=min(d[nej][i],d[nej][nei]+e[nei][i]);
				if(nej>0)d[nej-1][i]=min(d[nej-1][i],d[nej][nei]+e[nei][i]/2);
			}
		}
		int ans=INF;
		for(i=0;i<=c;i++)ans=min(ans,d[i][g-1]);
		printf("%d\n",ans);
	}
}