#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> pr;
typedef pair<int,pr > ppr;
const int INF=2<<28;
int main() {
	// your code goes here
	int c,n,m,s,d,a,b,f;
	while(cin >> c >> n >> m >> s >> d && c!=0){
		int longs [101][11]={};
		for(int i=1;i<=100;i++)
			for(int j=0;j<=10;j++)
				longs[i][j]=INF;
		priority_queue<ppr,vector<ppr>,greater<ppr> > p;
		vector<pr> root[101];
		for(int i=0;i<m;i++){
			cin >> a>>b >> f;
			root[a].push_back(pr(b,f));
			root[b].push_back(pr(a,f));
		}
		longs[s][0]=0;
		p.push(ppr(0,pr(0,s)));
		while(!p.empty()){
			int f=p.top().first,point=p.top().second.second,t=p.top().second.first;
			p.pop();
			if(longs[point][t]!=f) continue;
			for(int i=0;i<root[point].size();i++){
				int dir=root[point][i].first;
				if(f+root[point][i].second <= longs[dir][t]){
				longs[dir][t]=f+root[point][i].second;
				p.push(ppr(longs[dir][t],pr(t,dir)));
				}
				if(t+1<=c && f+root[point][i].second/2 <= longs[dir][t+1]){
				longs[dir][t+1]=f+root[point][i].second/2;
				p.push(ppr(longs[dir][t+1],pr(t+1,dir)));
				}
			}
		}
		int minim=INF;
		for(int i=0;i<=c;i++)
		minim=min(minim,longs[d][i]);
		cout << minim<< endl;
	}
	return 0;
}