#include <iostream>
#include <algorithm> 
using namespace std;

struct town {
	int n,tn[500],m[500],a[11];
};

town to[100];

int c,n,m,s,d;

void ans() {
	int i,j,k,f;
	for (i=0;i<n;i++) for (j=0;j<=c;j++) to[i].a[j]=9999999;
	for (i=0;i<=c;i++) to[s].a[i]=0;
	while(true)  {
		f=0;
		for (i=0;i<n;i++) for (j=0;j<to[i].n;j++) {
			 for (k=0;k<=c;k++) {
			 if (to[i].a[k]+(to[i].m[j])/2<to[to[i].tn[j]].a[k+1]) {to[to[i].tn[j]].a[k+1]=to[i].a[k]+(to[i].m[j])/2; f=1;}
			 if (to[i].a[k]+to[i].m[j]<to[to[i].tn[j]].a[k]) {to[to[i].tn[j]].a[k]=to[i].a[k]+to[i].m[j]; f=1;}
		    }
	    }
	    if (f==0) break;
	}
}
int main() {
	int i,a,b,x;
	while(cin >> c >> n >> m >> s >> d && n>0) {
		s--; d--;
		for (i=0;i<n;i++) to[i].n=0;
		for (i=0;i<m;i++) {
			cin >> a >> b >> x; a--; b--;
			to[a].tn[to[a].n]=b;  to[b].tn[to[b].n]=a;
			to[a].m[to[a].n]=to[b].m[to[b].n]=x;
			to[a].n++; to[b].n++;
		}
		ans();
		cout << to[d].a[c] << endl;
		}		 
	return 0;
}