#include <iostream>
#include <algorithm>

using namespace std;

const int inf = 999999;

int func(int dir[101][101], int c, int n, int s, int t)
{
	int r = inf;
	int dp[1<<10+1][101];
	fill(&dp[0][0], &dp[1<<10][100], inf);
	
	dp[(1<<c)-1][s] = 0;
	for(int i = (1<<c)-1; i >= 0; i--){
		r = min(r, dp[i][t]);
		for(int j = 1; j <= n; j++){
			for(int k = 0; k < c; k++){
				if(i >> k & 1){
					for(int l = 1; l <= n; l++){
						if(dp[j][l] >= 0){
							dp[i& ~(1 << k)][l] = min(dp[i & ~(1<<k)][l], (dp[i][j]+dir[j][l]/2));
						}
					}
				}
			}
		}
	}
	
	return r;
}

int main()
{
	int c, n, m, s, d, a, b, f;
	int dir[101][101];
	
	while(cin>>c>>n>>m>>s>>d && c && n && m && s && d){
		fill(&dir[0][0], &dir[100][100], inf);
		for(int i = 0; i <= 100; i++){
			dir[i][i] = 0;
		}
		while(m--){
			cin >> a >> b >> f;
			dir[a][b] = dir[b][a] = f;
		}
		
		cout << func(dir, c, n, s, d) << endl;
	}
	
	return 0;
}