#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <bitset>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>

#define X first
#define Y second
#define MP make_pair
typedef long long ll;
using namespace std;

int mindis[101], pre[101];
bool used[101];
int eCost[101][101];

int getPathSum(int c, int p, int g){
	vector<int> edge;
	edge.push_back(eCost[p][g]);
		
	int to = p;
	for(int from = pre[to]; from != 0; from = pre[from]){
		edge.push_back(eCost[from][to]);
		to = from;
	}

	sort(edge.begin(), edge.end());

	int idx = edge.size()-1;
	for(int i = 0; i < c; i++){
		edge[idx--] /= 2;
		if(idx < 0) break;
	}
	
	int ans = 0;
	for(int i = 0; i < edge.size(); i++){
		ans += edge[i];
	}

	return ans;
}

int main(){
	int c, n, m, s, d;
	while(cin >> c >> n >> m >> s >> d){
		if(c == 0 && n == 0 && m == 0 && s == 0 && d == 0) break;

		fill(mindis, mindis+101, 1<<30);
		fill(pre, pre+101, 0);
		fill(used, used+101, false);
		for(int i = 0; i < 101; i++) fill(eCost[i], eCost[i]+101, 1<<30);

		for(int i = 0; i < m; i++){
			int a, b, cost;
			cin >> a >> b >> cost;
			eCost[a][b] = cost;
			eCost[b][a] = cost;
		}

		mindis[s] = 0;
		vector<int> goals;

		//最短経路(ダイクストラ)
		while(true){
			int v = -1;
			for(int i = 1; i <= n; i++){
				if(!used[i] && (v == -1 || mindis[v] > mindis[i])) v = i;
			}

			if(v == d) break;
			used[v] = true;

			for(int i = 1; i <= n; i++){
				if(mindis[i] > mindis[v]+eCost[v][i]){
					if(i == d){
						//次がゴールならここでチケットを適用した総和を出して最終的な結果にする
						//それをgoalsに格納していく
						goals.push_back(getPathSum(c, v, i));
					}else{
						mindis[i] = mindis[v]+eCost[v][i];
						pre[i] = v;
					}
				}
			}
		}

		int minc = 100000000;
		for(int i = 0; i < goals.size(); i++){
			if(minc > goals[i]) minc = goals[i];
		}

		cout << minc << endl;
	}
	return 0;
}