#include<iostream>
#include<queue>
#include<map>
#define MAX 10000000
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
struct edge{
	int cost,to;
};
typedef pair<int,int> p;
typedef pair<int,p> P;
//`Pbg@»ÝÌ@v
int main(){
	int tic,n,m,s,a,b,g,d[11][101],f;
	//d ticket place
	while(cin>>tic>>n>>m>>s>>g,tic||n||m||s||g){
		s--;g--;
		//tic `Pbg
		//n Ì
		//m ´Ì
		//s¨g
		vector<edge> v[101];
		rep(i,m){
			cin>>a>>b>>f;
			a--;b--;
			edge c;
			c.cost=f;
			c.to=b;v[a].push_back(c);
			c.to=a;v[b].push_back(c);
		}
		rep(i,tic+1)
		rep(j,n){
			if(j==s)
			d[i][j]=0;
			else
			d[i][j]=MAX;
		}
		int nowticket,nowplace,nowsum;
		priority_queue<P,vector<P>,greater<P> > que;
		P now;
		que.push(P(tic,p(s,0)));
		while(!que.empty()){
			now=que.top();
			que.pop();
			nowticket=now.first;
			nowplace=now.second.first;
			nowsum=now.second.second;
			if(nowplace==g){
				cout<<nowsum<<endl;
				break;
			}
			if(d[nowticket][nowplace]<nowsum)
				continue;
			rep(i,(int)v[nowplace].size()){
				edge e=v[nowplace][i];
				if(nowticket>0){
					if(d[nowticket-1][e.to]>e.cost/2+nowsum){
						d[nowticket-1][e.to]=e.cost/2+nowsum;
						que.push(P(nowticket-1,p(e.to,d[nowticket-1][e.to])));
					}
				}
				if(d[nowticket][e.to]>e.cost+nowsum){
						d[nowticket][e.to]=e.cost+nowsum;
						que.push(P(nowticket,p(e.to,d[nowticket][e.to])));
				}
			}
		}
	}
	return 0;
}