#include<iostream>
#include<functional>
#include<queue>

#define INFTY 1<<30
#define N 101
#define C 11
#define CONNECTED 1
#define IN_QUEUE 1

using namespace std;

int cost[N][C];
bool vis[N][C];
int W[N][N];
int G[N][N];

class Node{
public:
	Node():id(0),cost(INFTY),c(0){}
	int id;
	int cost;
	int c;
	bool operator>(const Node &t)const{return this->cost > t.cost;}
};

void Dijkstra( Node s ){
	priority_queue<Node,vector<Node>,greater<Node>> pq;

	pq.push( s );

	while( !pq.empty() ){
		Node p = pq.top();

		pq.pop();

		if( vis[p.id][p.c] )
			continue;
		vis[p.id][p.c] = true;
		cost[p.id][p.c] = min( cost[p.id][p.c], p.cost );

		for(int i = 0; i < N; ++i){
			if( G[p.id][i] == CONNECTED ){
				Node np;

				np.id = i;
				np.cost = cost[p.id][p.c] + W[p.id][i];
				np.c = p.c;
				pq.push( np );
				if( p.c > 0 ){
					np.cost = cost[p.id][p.c] + (W[p.id][i]/2);
					np.c = p.c - 1;
					pq.push( np );
				}
			}
		}
	}
}
void ResetGraph(){
	for(int i = 0; i < N; ++i){
		for(int j = 0; j < C; ++j){
			cost[i][j] = INFTY;
			vis[i][j] = false;
		}
		for(int j = 0; j < N; ++j){
			G[i][j] = 0;
			W[i][j] = 0;
		}
	}
}
int main(){
	while( true ){
		int c, n, m, s, d;
		int ans = INFTY;
		Node start;
		
		cin >> c >> n >> m >> s >> d;
		if( !(c||n||m||s||d) )
			break;

		ResetGraph();
		for(int i = 0; i < m; ++i){
			int a, b, f;

			cin >> a >> b >> f;
			G[a][b] = G[b][a] = CONNECTED;
			W[a][b] = W[b][a] = f;
		}
		start.id = s;
		start.cost = 0;
		start.c = c;

		Dijkstra( start );

		for(int i = 0; i < C; ++i){
			ans = min(ans, cost[d][i]);
		}
		cout << ans << '\n';
	}
	return 0;
}