#include <bits/stdc++.h>
using namespace std;

struct NODE{
	int x,t,c;
};
bool operator < (const NODE &a,const NODE &b){
	return a.c > b.c;
}
int main(){
	int c,n,m,s,d;
	while(cin >> c >> n >> m >> s >> d && c ){
		s--,d--;
		vector<NODE> g[110];
		for(int i = 0 ; i < m ; i++){
			int a,b,c;
			cin >> a >> b >> c;
			--a,--b;
			g[a].push_back({b,0,c});
			g[a].push_back({b,1,c/2});
			g[b].push_back({a,0,c});
			g[b].push_back({a,1,c/2});
		}
		priority_queue<NODE> Q;
		Q.push({s,c,0});
		int done[110][11] = {};
		while(Q.size()){
			NODE q = Q.top(); Q.pop();
			if( q.t < 0 ) continue;
			if( done[q.x][q.t]++ ) continue;
			if( q.x == d ){
				cout << q.c << endl;
				break;
			}
			for( auto e : g[q.x] ) Q.push({e.x,q.t-e.t,q.c+e.c});
		}
		
		
	}	
}