#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;

int c, n, m, S, D;

struct EDGE { int to, cost; };
vector<EDGE> g[100];

struct STATE
{
	int cost, now, num;
	
	bool operator<(const STATE t)const{
		return cost > t.cost;
	}
};

int d[100][11];

void init()
{
	for (int i = 0; i < 100; i++){
		g[i].clear();
	}
	for (int i = 0; i < 100; i++){
		for (int j = 0; j <= 10; j++){
			d[i][j] = INF;
		}
	}
}

void search(int s)
{	
	for (int i = 0; i <= 10; i++){
		d[s][i] = 0;
	}
	
	priority_queue<STATE, vector<STATE> > que;
	que.push({0, s, 0});
	while (!que.empty()){
		STATE st = que.top(); que.pop();
		if (d[st.now][st.num] < st.cost) continue;
		
		for (int i = 0; i < g[st.now].size(); i++){
			EDGE e = g[st.now][i];
			if (d[e.to][st.num] > d[st.now][st.num] + e.cost){
				d[e.to][st.num] = d[st.now][st.num] + e.cost;
				que.push({d[e.to][st.num], e.to, st.num});
			}
		}
		
		if (st.num == c) continue;
		
		for (int i = 0; i < g[st.now].size(); i++){
			EDGE e = g[st.now][i];
			if (d[e.to][st.num + 1] > d[st.now][st.num] + e.cost / 2){
				d[e.to][st.num + 1] = d[st.now][st.num] + e.cost / 2;
				que.push({d[e.to][st.num + 1], e.to, st.num + 1});
			}
		}
	}
}

int main()
{
	while (scanf("%d %d %d %d %d", &c, &n, &m, &S, &D), c){
		S--; D--;
		
		init();
		
		for (int i = 0; i < m; i++){
			int a, b, f;
			scanf("%d %d %d", &a, &b, &f);
			a--; b--;
			
			g[a].push_back({b, f});
			g[b].push_back({a, f});
		}
		
		search(S);
		int mini = INF;
		for (int i = 0; i <= c; i++) mini = min(mini, d[D][i]);
		printf("%d\n", mini);
	}
	
	return 0;
}