#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int ijk[200][20];
int v[200][20];
vector<pair<int,int> >g[200];
int main(){
	int a,b,c,d,e;
	while(scanf("%d%d%d%d%d",&a,&b,&c,&d,&e),b){
		d--;e--;
		for(int i=0;i<200;i++)g[i].clear();
		for(int i=0;i<c;i++){
			int p,q,r;
			scanf("%d%d%d",&p,&q,&r);
			p--;q--;
			g[p].push_back(make_pair(q,r));
			g[q].push_back(make_pair(p,r));
		}
		for(int i=0;i<b;i++){
			for(int j=0;j<=a;j++){
				v[i][j]=0;
				ijk[i][j]=999999999;
			}
		}
		ijk[d][a]=0;
		priority_queue<pair<int,pair<int,int> > >Q;
		Q.push(make_pair(0,make_pair(d,a)));
		while(Q.size()){
			int cost=-Q.top().first;
			int at=Q.top().second.first;
			int nk=Q.top().second.second;
			Q.pop();
			if(v[at][nk])continue;
			for(int i=0;i<g[at].size();i++){
				if(!v[g[at][i].first][nk]&&ijk[g[at][i].first][nk]>cost+g[at][i].second){
					ijk[g[at][i].first][nk]=cost+g[at][i].second;
					Q.push(make_pair(-ijk[g[at][i].first][nk],make_pair(g[at][i].first,nk)));
				}
				if(nk&&!v[g[at][i].first][nk-1]&&ijk[g[at][i].first][nk-1]>cost+g[at][i].second/2){
					ijk[g[at][i].first][nk-1]=cost+g[at][i].second/2;
					Q.push(make_pair(-ijk[g[at][i].first][nk-1],make_pair(g[at][i].first,nk-1)));
				}
			}
		}
		int ret=999999999;
		for(int i=0;i<=a;i++)ret=min(ret,ijk[e][i]);
		printf("%d\n",ret);
	}
}