#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 100000000;
const int C_MAX = 10;
const int N_MAX = 100;

//街の情報 <残りの割引券, 街の番号>
typedef pair<int, int> T;
//地点情報 <最小コスト, <残りの割引券, 街の番号>>
typedef pair<int, T> P;

//c: チケットの枚数(1 <= c <= 10)
//n: バスをつなぐ町の数(2 <= n <= 100)
//m: バスの路線数(1 <= m <= 500)
//s: 出発地点
//d: 目的地
int c, n, m, s, d;
//cost[町の番号][残りの割引券] = 費用
int cost[N_MAX][C_MAX + 1];

//すでにコストの最適値が決定済みかどうか
bool flag[N_MAX][C_MAX + 1];

//町間の料金
int line[N_MAX][N_MAX];

typedef priority_queue<P, vector<P>, greater<P> > Q;
Q dp_q;

int dijkstra(){
	while(!dp_q.empty()){
		P p = dp_q.top(); dp_q.pop();
		T &t = p.second;

		//p.first: 最小コスト
		//t.first: 残りの割引券
		//t.second: 町番号

		//既に最適値なのかどうかを調べる
		if(flag[t.second][t.first])	continue;
		flag[t.second][t.first] = true;

		if(t.second == d){
			return p.first;
		}

		//すべての頂点に対して割引券を使ったか使ってないかを決める
		for(int i = 0; i < n; i++){
			//割引券を使わなかった場合のiのコスト
			//(t.secondでの最小コスト + t.second -> iの料金)が割引券がt.firstの時の町iのコストより小さい
			//時にc[i][t.first]を更新
			if(cost[i][t.first] > p.first + line[t.second][i]){
				cost[i][t.first] = p.first + line[t.second][i];
				dp_q.push(P(p.first + line[t.second][i], T(t.first, i)));
			}

			//割引券を使った場合のiのコスト
			//(t.secondでの最小コスト + t.second -> iの料金の半分)が
			//割引券がt.first - 1の時の町iのコストより小さい時に
			//c[i][t.first - 1]を更新
			if(t.first > 0 && cost[i][t.first - 1] > p.first + line[t.second][i] / 2){
				cost[i][t.first-1] = p.first + line[t.second][i] / 2;
				dp_q.push(P(p.first + line[t.second][i] / 2, T(t.first - 1, i)));
			}
		}
	}

	return INF;
}

void solve(){
	for(int i = 0; i < N_MAX; i++){
		for(int j = 0; j < C_MAX; j++){
			cost[i][j] = INF;
			flag[i][j] = false;
		}
	}

	dp_q.push(P(0, T(c, s)));

	cout << dijkstra() << endl;
}

int main(void){
	int a, b, f;

	while(true){
		cin >> c >> n >> m >> s >> d;
		if(!c && !n && !m && !s && !d)	break;
		s--; d--;
		
		for(int i = 0; i < N_MAX; i++){
			for(int j = 0; j < N_MAX; ++j){
				line[i][j] = INF;
			}
		}

		for(int i = 0; i < m; i++){
			cin >> a >> b >> f;
			a--;	b--;
			line[a][b] = f;
			line[b][a] = f;
		}

		solve();
	}
  return 0;
}