#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<iostream>

using namespace std;

#define PII pair<int,int>
#define PPI pair<int,PII>

#define INF 1000000000

int c;	//øÌ	   1 <= c <=    10
int n;	//¬Ì		   2 <= n <=   100
int m;	//oXÌHü	   1 <= m <=   500
int s,g;//X^[gAS[n_
//int cost[512][512];		//[i][j]Åi©çjÖÌRXg
vector<PII> cost[512];		//firstªto secondªRXg

int d[128][16];

priority_queue< PPI, vector<PPI>, greater<PPI> > Q;
//first ÅZ£ ,second.first ¸_,second.second øðgÁ½


void dijkstra(int s){
	for(int i = 0; i < 128; i++){
		for(int j = 0; j < 16; j++){
			d[i][j] = INF;
		}
	}
	
	d[s][0] = 0;
	
	Q.push(PPI(0,PII(s,0)));
	
	while( !Q.empty() ){
		PPI ppi = Q.top();
		Q.pop();
		int v = ppi.second.first;
		int ca = ppi.second.second;
		
		if( d[v][ca] < ppi.first )continue;
		
		for(int i = 0; i < cost[v].size(); i++){
			PII a = cost[v][i];
			if(d[a.first][ca] > d[v][ca] + a.second ){
				d[a.first][ca] = d[v][ca] + a.second;
				Q.push(PPI(d[a.first][ca],PII(a.first,ca)));
			}
			if(ca < c){
				if(d[a.first][ca+1] > d[v][ca] + a.second/2 ){
					d[a.first][ca+1] = d[v][ca] + a.second/2;
					Q.push(PPI(d[a.first][ca+1],PII(a.first,ca+1)));
				}
			}
		}
	}
}


int main(void){
	
	while(scanf("%d%d%d%d%d", &c, &n, &m, &s, &g) && n != 0){
		int from, to, cos;
		int ans = INF;
		for(int i  =0; i < m; i++){
			scanf("%d%d%d", &from, &to, &cos);
			cost[from].push_back(PII(to,cos));
			cost[to].push_back(PII(from,cos));
		}
		
		dijkstra(s);
		
		for(int i = 0; i <= c; i++){
			ans = min(d[g][i],ans);
		}
		for(int i = 0; i < 512; i++){
			cost[i].clear();
		}
		printf("%d\n",ans);
	}
	return 0;
}