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

struct town {
	int n,tn[500],m[500],mn,mm;
};

town to[100];

int mm,c,n,m,s,d,p[100],p2[100];

void ans(int k,int h,int g) {
	int i,a=0;
	if (g>=mm*2) return;
	if (h==d) { 
		for (i=0;i<k;i++) p2[i]=p[i];
		sort(p2,p2+k,greater<int>());
		for (i=0;i<k;i++) if (i<c) a+=p2[i]/2; else a+=p2[i];
		if (a<mm) mm=a;
		return;
	 }
	for (i=0;i<to[h].n;i++) {
		p[k]=to[h].m[i];
		if (to[to[h].tn[i]].mn==1) continue;
		to[to[h].tn[i]].mn=1;
		ans(k+1,to[h].tn[i],g+p[k]);
		to[to[h].tn[i]].mn=0;
	}   
   }

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; to[i].mn=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++;
		}
		mm=99999999;
		to[s].mn=1;
		ans(0,s,0);
		cout << mm << endl;
    }		 
	return 0;
}