#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

#define MAX_V 200000

struct edge{
	int to;
	long long int cost;
    edge(int to_, long long int cost_){
        to = to_;
        cost = cost_;
    }
};

vector<edge> G[MAX_V];
long long int d[MAX_V];

// O(ElogV)

void shortest_path(int s, int V){
	
	priority_queue<P, vector<P>, greater<P> > que;
	
	for(int i = 0; i < V; i++){
		d[i] = INF;
	}
	d[s] = 0;
	
	que.push(P(0, s));
	
	while(!que.empty()){
		
		P p = que.top();
		que.pop();
		
		int v = p.second;
		
		if(d[v] < p.first){
			continue;
		}
		
		for(int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			if(d[e.to] > e.cost + d[v]){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main(){
	while(true){
		int c, n, m, s, g;
		cin >> c >> n >> m >> s >> g;
		if(c == 0){
			break;
		}
		s -= 1;
		g -= 1;
		for(int i = 0; i < m; i++){
			int a, b, f;
			cin >> a >> b >> f;
			a -= 1;
			b -= 1;
			G[a].emplace_back(b, f);
			G[b].emplace_back(a, f);
			for(int j = 0; j < c; j++){
				G[a + n * j].emplace_back(b + n * (j + 1), f / 2);
				G[b + n * j].emplace_back(a + n * (j + 1), f / 2);
			}
			for(int j = 0; j <= c; j++){
				G[a + n * j].emplace_back(b + n * j, f);
				G[b + n * j].emplace_back(a + n * j, f);
			}
		}
		shortest_path(s, n * (c + 1));
		long long int ans = INF;
		for(int i = 0; i <= c; i++){
			ans = min(ans, d[g + n * i]);
		}
		cout << ans << endl;
		for(int i = 0; i < n * (c + 1); i++){
			G[i].clear();
		}
	}
	return 0;
}
