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

#define INF (1e+9)

#define MAX_N 100
#define MAX_C 10

using namespace std;

typedef struct edge{
	int to;
	int cost;
	int used;
	edge(){}
	edge(int _to,int _cost,int _used){
		to = _to;
		cost = _cost;
		used = _used;
	}
	bool operator<(const edge &a)const{
		if(cost == a.cost) return to > a.to;
		return cost > a.cost;	//for ASC
	}
}edge;


int cost[MAX_N + 1][MAX_N + 1];
int sum[MAX_N + 1][MAX_C + 1];
priority_queue<edge > pque;

int C;
int N,M;
int S,D;

void init(){
	for(int i = 0;i <= MAX_N;i++){
		for(int j = 0;j <= MAX_N;j++){
			cost[i][j] = INF;
		}
	}
	for(int i = 0;i <= MAX_N;i++){
		for(int j = 0;j <= MAX_C;j++){
			sum[i][j] = INF;
		}
	}
	return ;
}

int solve(){
	int res;

	pque.push(edge(S,0,0));

	while(!pque.empty()){
		edge e = pque.top();pque.pop();
		if(sum[e.to][e.used] != INF) continue;
		sum[e.to][e.used] = e.cost;
		for(int i = 1;i <= N;i++){
			if(cost[e.to][i] != INF){
				int _cost = e.cost + cost[e.to][i];
				pque.push(edge(i,_cost,e.used));
				if(e.used < C){
					_cost = e.cost + cost[e.to][i] / 2;
					pque.push(edge(i,_cost,e.used + 1));
				}
			}
		}
	}

	res = INF;
	for(int i = 0;i <= 10;i++){
		res = min(res,sum[D][i]);
	}

	return res;
}

int main(){

	while(true){
		init();
		scanf("%d%d%d%d%d",&C,&N,&M,&S,&D);
		if(C == 0) break;
		int _u,_v,_cost;
		for(int i = 0;i < M;i++){
			scanf("%d%d%d",&_u,&_v,&_cost);
			cost[_u][_v] = _cost;
			cost[_v][_u] = _cost;
		}
		
		int ans = solve();

		/*for(int i = 1;i <= N;i++){
			printf("###");
			for(int j = 0;j <= C;j++){
				printf(" %d",sum[i][j]);
			}
			puts("");
		}*/
		printf("%d\n",ans);

	}

	return 0;
}