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

const int INF = 1e9;

//<最小コスト, 町番号>
typedef pair<int, int> P;
struct edge{int to, cost;};
int c, n, m, s, dist;
vector<edge> G[100];
//割引券が残りiの時のj地点における最小コスト
int d[10][100];

void dijkstra(int s, int a){
	priority_queue<P, vector<P>, greater<P> > Q;
	for(int i = 0; i < n; i++) d[a][i] = INF;
	d[a][s] = 0;
	Q.push(P(0, s));

	while(!Q.empty()){
		P p = Q.top(); Q.pop();
		int v = p.second;

		if(d[a][v] < p.first)	continue;
		for(int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			
			//割引券を使った時と使ってない時でよりコストが小さい時をdmに代入
			int dm;
			if(a == 0)	dm = d[a][v] + e.cost;
			else dm = min(d[a][v] + e.cost, d[a-1][v] + e.cost / 2);

			if(d[a][e.to] > dm){
				d[a][e.to] = dm;
				Q.push(P(d[a][e.to], e.to));
			}
		}
	}
}

int main(void){
	while(true){
		cin >> c >> n >> m >> s >> dist;
		s--; dist--;
		if(!c)	break;

		edge e;
		for(int i = 0; i < m; i++){
			int a, b, f;
			cin >> a >> b >> f;
			a--; b--;
			e.to = b; e.cost = f;
			G[a].push_back(e);
			e.to = a;
			G[b].push_back(e);
		}

		int ans = INF;

		for(int i = 0; i <= c; i++){
			dijkstra(s, i);
		}

		cout << d[c][dist] << endl;

		for(int i = 0; i < 100; i++) G[i].clear();
	}

  return 0;
}