#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> PP;
int c,n,m,s,d;
vector<P> G[101];
int cost[101][11];
int INF=10000000;

int dijkstra(int s){
	priority_queue<PP, vector<PP>, greater<PP> >que;
	for(int i=0;i<=100;i++){
		for(int j=0;j<=10;j++){
			cost[i][j]=INF;
		}
	}
	cost[s][0]=0;
	que.push(PP(P(s,0),0));
	while(que.size()){
		PP p=que.top();que.pop();
		int v=p.first.first,d=p.first.second,k=p.second;
		if(cost[v][k]<d)continue;
		for(int i=0;i<G[v].size();i++){
			P e=G[v][i];
			if(cost[e.first][k]>cost[v][k]+e.second){
				cost[e.first][k]=cost[v][k]+e.second;
				que.push(PP(P(e.first,cost[e.first][k]),k));
			}
		}
		if(k<c)for(int i=0;i<G[v].size();i++){
			P e=G[v][i];
			if(cost[e.first][k+1]>cost[v][k]+e.second/2){
				cost[e.first][k+1]=cost[v][k]+e.second/2;
				que.push(PP(P(e.first,cost[e.first][k+1]),k+1));
			}
		}
	}

	int ans=INF;
	for(int i=0;i<=10;i++){
		ans=min(ans,cost[d][i]);
	}
	return ans;
}

int main(void){
	while(1){
		scanf("%d%d%d%d%d",&c,&n,&m,&s,&d);
		if(c==0 && n==0 && m==0 && s==0 && d==0)break;
		for(int i=0;i<=100;i++)G[i].clear();
		for(int i=0;i<m;i++){
			int a,b,f;
			scanf("%d%d%d",&a,&b,&f);
			G[a].push_back(P(b,f));
			G[b].push_back(P(a,f));
		}
		cout << dijkstra(s) << endl;
	}
    return 0;
}