#include <iostream>
#include <algorithm>

const int MAX_N = 100, MAX_C = 11, INF = 1 << 24;
int dist[MAX_C][MAX_N], used[MAX_C][MAX_N], cost[MAX_N][MAX_N];
int c, n, m, s, d;

void dijkstra(int s){
	for(int i=0;i<MAX_C;i++){
		std::fill(dist[i], dist[i]+MAX_N, INF);
		std::fill(used[i], used[i]+MAX_N, 0);
	}

	dist[0][s] = 0;

	while(true){
		int u = -1, v;
		for(int i=0;i<=c;i++){
			for(int j=0;j<n;j++){
				if(!used[i][j] && (u == -1 || dist[i][j] < dist[u][v]))
					u = i, v = j;
			}
		}

		if(u == -1)break;
		used[u][v] = 1;


		for(int i=0;i<n;i++){
			dist[u][i] = std::min(dist[u][i], dist[u][v] + cost[v][i]);
			if(u+1 < n)
				dist[u+1][i] = std::min(dist[u+1][i], dist[u][v] + cost[v][i] / 2);
		}
	}
}

int main(){
	while(std::cin >> c >> n >> m >> s >> d, c){

		for(int i=0;i<MAX_C;i++){
			std::fill(cost[i], cost[i]+MAX_C, INF);
		}

		for(int i=m;i--;){
			int a, b, f;
			std::cin >> a >> b >> f;
			cost[a-1][b-1] = f;
			cost[b-1][a-1] = f;
		}

		dijkstra(s-1);

		int res = INF;
		for(int i=0;i<=c;i++){
			res = std::min(res, dist[i][d-1]);
		}

		std::cout << res << std::endl;
	}
}