#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct Edge{
	int s,d,w,n;
	Edge(){}
	Edge(int s,int d,int w,int n=0):s(s),d(d),w(w),n(n){}
	bool operator<(const Edge& e)const{return w<e.w;}
	bool operator>(const Edge& e)const{return w>e.w;}
};

const int INFTY=1<<29;

int main()
{
	for(int c,n,m,s,d;cin>>c>>n>>m>>s>>d,c|n|m|s|d;){
		s--; d--;
		vector<vector<Edge> > g(n);
		for(int i=0;i<m;i++){
			int s,d,w; cin>>s>>d>>w;
			s--; d--;
			g[s].push_back(Edge(s,d,w));
			g[d].push_back(Edge(d,s,w));
		}
		priority_queue<Edge,vector<Edge>,greater<Edge> > pq;
		vector<vector<int> > cost(n,vector<int>(c+1,INFTY));
		pq.push(Edge(-1,s,0,0));
		while(pq.size()){
			Edge cur=pq.top(); pq.pop();
			if(cost[cur.d][cur.n]!=INFTY)
				continue;
			cost[cur.d][cur.n]=cur.w;
			for(int i=0;i<g[cur.d].size();i++){
				Edge& e=g[cur.d][i];
				pq.push(Edge(e.s,e.d,cur.w+e.w,cur.n));
				if(cur.n<c)
					pq.push(Edge(e.s,e.d,cur.w+e.w/2,cur.n+1));
			}
		}
		
		cout<<*min_element(cost[d].begin(),cost[d].end())<<endl;
	}
	
	return 0;
}