#include <iostream>
#include <queue>
#include <climits>
#include <vector>
using namespace std;
typedef pair<pair<int,int>,int> NODE;
#define cost first.first
#define ticket first.second 
#define pos second
#define ppp(a,b,c) make_pair(make_pair(a,b),c)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<21)

int info[100][100];
int n;

int dijk(int a,int b,int c){
	priority_queue<NODE,vector<NODE>,greater<NODE> > que;
	int memo[100][11];
	rep(i,100)rep(j,11)memo[i][j] = INF;
	//rep(j,11)memo[a][j] = 0;
	
	que.push(ppp(0,c,a));
	while( !que.empty() ){
		NODE q = que.top();que.pop();
		
		if(memo[q.pos][q.ticket]<=q.cost)continue;
		
		if(q.pos == b)return q.cost;
		
		memo[q.pos][q.ticket] = q.cost;
		
		for(int i=0;i<n;i++){
			que.push(ppp(info[q.pos][i]+q.cost ,q.ticket,i));
			if(q.ticket)que.push(ppp(info[q.pos][i]/2+q.cost ,q.ticket-1,i));

		}
	}
	
	/*ツ個ゥツづつつゥツづァツづ按つゥツづつス*/
	return -1;
}
int main(){
	int c,m,s,d,a,b,f;
	while(cin >> c >> n >> m >> s >> d ,c ){
		s--;d--;
		rep(i,100)rep(j,100)info[i][j]=INF*2;
		
		for(int i=0;i<m;i++){
			cin >> a >> b >> f;
			a--;b--;
			info[a][b] = info[b][a] = f;
		}
		cout << dijk(s,d,c) << endl;
	}
}