#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1e+9
using namespace std;

struct edge{ int to; int cost; };
typedef pair<int,int> P;

vector<edge> graph[100];
int cost[10][100];
int V;

void dijkstra(int dijk_s,int a){
	priority_queue<P,vector<P>,greater<P> > dijk_que;
	for(int i = 0;i < V;i++) cost[a][i] = INF;
	cost[a][dijk_s] = 0;
	dijk_que.push(make_pair(0,dijk_s));
	while(!dijk_que.empty()){
		P dijk_p = dijk_que.top();
		dijk_que.pop();
		int dijk_v = dijk_p.second;
		//if(cost[a][dijk_v] < dijk_p.first) continue;
		for(int i = 0;i < graph[dijk_v].size();i++){
			edge dijk_e = graph[dijk_v][i];
			int cmin;
			if(a == 0) cmin = cost[a][dijk_v] + dijk_e.cost;
			else cmin = min(cost[a][dijk_v] + dijk_e.cost,cost[a - 1][dijk_v] + dijk_e.cost / 2);
			if(cost[a][dijk_e.to] > cmin){
				cost[a][dijk_e.to] = cmin;
				dijk_que.push(make_pair(cost[a][dijk_e.to],dijk_e.to));
			}
		}
	}
}

int main(){
	int c,m,s,d;
	while(1){
	cin >> c >> V >> m >> s >> d;
	if(c == 0) break;
	for(int i = 0;i < m;i++){
		int a,b,f;
		cin >> a >> b >> f;
		graph[a - 1].push_back({b - 1,f});
		graph[b - 1].push_back({a - 1,f});
	}
	for(int i = 0;i <= c;i++){
		dijkstra(s - 1,i);
	}
	cout << cost[c][d - 1] << endl;
	for(int i = 0;i < V;i++) graph[i].clear();
	}
	return 0;
}