#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)

struct Edge {
	int v, f, c;
	bool operator > (const Edge& e) const { return f > e.f; }
};

int c, n, m, s, d;
vector< vector< Edge > > edges;

int cost[111][11];

int djk() {
	for_(i,0,111) for_(j,0,11) cost[i][j] = (int)1e9;
	
	priority_queue< Edge, vector< Edge >, greater< Edge > > que;
	que.push(Edge{s, 0, c});
	cost[s][c] = 0;
	
	while (!que.empty()) {
		Edge e = que.top(); que.pop();
		
		for (Edge& ei : edges[e.v]) {
			if (cost[ei.v][e.c] > e.f + ei.f) {
				cost[ei.v][e.c] = e.f + ei.f;
				que.push(Edge{ei.v, e.f + ei.f, e.c});
			}
			
			if (e.c > 0 && cost[ei.v][e.c - 1] > e.f + ei.f / 2) {
				cost[ei.v][e.c - 1] = e.f + ei.f / 2;
				que.push(Edge{ei.v, e.f + ei.f / 2, e.c - 1});
			}
		}
	}
	
	int ans = (int)1e9;
	for_(i,0,11) ans = min(ans, cost[d][i]);
	
	return ans;
}

int main() {
	while (cin >> c >> n >> m >> s >> d, n) {
		--s; --d;
		
		edges.assign(n, vector< Edge >());
		
		for_(i,0,m) {
			int a, b, f;
			cin >> a >> b >> f;
			--a; --b;
			edges[a].push_back(Edge{b, f, 0});
			edges[b].push_back(Edge{a, f, 0});
		}
		
		cout << djk() << endl;
	}
}