#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> _P;
typedef pair<int,_P> P;
int main() {
	int c,n,m,s,d;
	int a,b,f;
	int i,ans;
	int cost1[100][100],cost2[100][11];
	priority_queue<P,vector<P>,greater<P> > que;
	while(scanf("%d%d%d%d%d",&c,&n,&m,&s,&d),c) {
		fill(cost1[0],cost1[0]+100*100,1<<27);
		fill(cost2[0],cost2[0]+100*11,1<<27);
		for(i=0;i<m;i++) {
			scanf("%d%d%d",&a,&b,&f);
			cost1[a-1][b-1]=cost1[b-1][a-1]=min(cost1[a-1][b-1],f);
		}
		while(!que.empty()) que.pop();
		que.push(P(0,_P(s-1,0)));
		cost2[s-1][0]=0;
		while(!que.empty()) {
			P p=que.top();que.pop();
			if(cost2[p.second.first][p.second.second]<p.first) continue;
			for(i=0;i<n;i++) {
				if((p.first+cost1[p.second.first][i])<cost2[i][p.second.second]) {
					cost2[i][p.second.second]=p.first+cost1[p.second.first][i];
					que.push(P(cost2[i][p.second.second],_P(i,p.second.second)));
				}
				if(p.second.second+1<=c&&(p.first+cost1[p.second.first][i]/2)<cost2[i][p.second.second+1]) {
					cost2[i][p.second.second+1]=p.first+cost1[p.second.first][i]/2;
					que.push(P(cost2[i][p.second.second+1],_P(i,p.second.second+1)));
				}
			}
		}
		ans=(1<<27);
		for(i=0;i<=c;i++)ans=min(ans,cost2[d-1][i]);
		printf("%d\n",ans);
	}
}