#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;

using namespace std;

int minimum,num_ticket,num_town,m,start,goal,costTable[101][101];


struct Info{
	Info(){
		for(int i = 1; i <= num_town; i++){
			visited[i] = false;
		}
		current_town = 0;
		index = 0;
	}
	bool visited[102];
	int current_town,index,costs[102];

};

void func(Info info){

	//?¢?????????????????¨??????????<???info.costs????????????????????§???????????¨????????????>
	int sum = 0;

	for(int i = 0; i < info.index;i++){
		if(i < num_ticket){
			sum += info.costs[i]/2;
		}else{
			sum += info.costs[i];
		}
	}

	if(info.current_town == goal){ //?????¨????¢????????????????????°????????¶????????????????????????????
		minimum = min(minimum,sum);
		return;
	}else{
		if(sum >= minimum){
			return;
		}
	}

	for(int i = 1; i <= num_town; i++){
		if(costTable[info.current_town][i] != -1 && info.visited[i] == false){ //??????????????¨?????????????¨????????????¨???????????´???
			Info new_info;
			for(int k = 1; k <= num_town; k++)new_info.visited[k] = info.visited[k];
			new_info.visited[i] = true;
			new_info.current_town = i;
			for(int k = 0; k < info.index;k++)new_info.costs[k] = info.costs[k];

			//?????\?????????
			if(info.index == 0 || info.costs[info.index-1] <= costTable[info.current_town][i]){
				new_info.costs[info.index] = costTable[info.current_town][i];
				new_info.index = info.index+1;
				func(new_info);
			}else{
				for(int k = 0; k < info.index; k++){
					if(new_info.costs[k] < costTable[info.current_town][i]){
						for(int p = info.index-1; p >= k; p--){
							new_info.costs[p+1] = new_info.costs[p];
						}
						new_info.costs[k] = costTable[info.current_town][i];
						break;
					}
				}
				new_info.index = info.index+1;
				func(new_info);
			}
		}
	}
}

int main(){

	int from,to,fee;

	while(true){
		scanf("%d %d %d %d %d",&num_ticket,&num_town,&m,&start,&goal);
		if(num_ticket == 0 && num_town == 0 && m == 0 && start == 0 && goal == 0)break;

		minimum = 2000000000;

		for(int i = 1; i <= num_town; i++){
			for(int k = 1; k <= num_town; k++)costTable[i][k] = -1;
		}

		for(int i = 0; i < m; i++){
			scanf("%d %d %d",&from,&to,&fee);
			costTable[from][to] = fee;
			costTable[to][from] = fee;
		}

		Info info;

		info.current_town = start;
		info.visited[start] = true;

		func(info);

		printf("%d\n",minimum);
	}


	return 0;
}