#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

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

struct Info{
	Info(){
		for(int i = 0; i < 100; i++){
			visited[i+1] = false;
			cost[i] = -1;
		}
		current_town = 0;
		index = 0;
	}
	bool visited[101];
	int current_town,cost[100],index;
};

void func(Info info){
	if(info.current_town == goal){

		for(int i = 1; i <= info.index-1; i++){
			for(int k = info.index-1; k >= i; k--){
				if(info.cost[k] > info.cost[k-1])swap(info.cost[k],info.cost[k-1]);
			}
		}
		int sum = 0;

		if(num_ticket >= info.index){
			for(int i = 0; i < info.index; i++){
				sum += info.cost[i];
			}
			sum /= 2;
			minimum = min(minimum,sum);
		}else{
			for(int i = 0; i < num_ticket; i++){
				sum += info.cost[i]/2;
			}
			for(int i = num_ticket; i < info.index; i++){
				sum += info.cost[i];
			}

			minimum = min(minimum,sum);
		}

		return;
	}

	for(int i = 1; i <= num_town; i++){
		if(info.visited[i] == false && costTable[info.current_town][i] != -1){
			Info new_info;

			for(int k = 0; k < 100; k++){
				new_info.visited[k+1] = info.visited[k+1];
				new_info.cost[k] = info.cost[k];
			}
			new_info.visited[i] = true;
			new_info.current_town = i;
			new_info.index = info.index;
			new_info.cost[new_info.index++] = costTable[info.current_town][i];
			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;
}