#include <vector>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <queue>
#include <string.h>
#include <stdio.h>

typedef long long ll;
using namespace std;

typedef vector<vector<pair<int, int> > > graph_t;
typedef vector<tuple<int, int, int>> edges_t;
const int INF = 1e9+1;

vector<int> dijkstra(int N, const graph_t &g, int s)
{
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
	vector<int> cost(N, INF);
	q.push(make_pair(0, s));
	cost[s] = 0;
	while (!q.empty()) {
		pair<int, int> p = q.top();
		q.pop();
		int c = p.first;
		int v = p.second;
		if (cost[v] < c)
			continue;
		for (vector<pair<int, int> >::const_iterator i = g[v].begin(); i != g[v].end(); ++i) {
			if (cost[i->first] > cost[v] + i->second) {
				cost[i->first] = cost[v] + i->second;
				q.push(make_pair(cost[i->first], i->first));
			}
		}
	}
	return cost;
}

int solve(int c, int n, int s, int d, const edges_t &edges)
{
	graph_t g;
	g.resize(n);
	for (auto i = edges.begin(); i != edges.end(); i++) {
		int a, b, f;
		tie(a, b, f) = *i;
		g[a].emplace_back(b, f);
		g[b].emplace_back(a, f);
	}

	vector<vector<int>> cost; // cost[?????????????????°][????????????]
	cost.resize(c+1);
	for (auto i = cost.begin(); i != cost.end(); ++i) {
		i->resize(n, INF);
	}
	cost[c] = dijkstra(n, g, s);
	for (int w = c-1; w >= 0; w--) {
		cost[w][s] = 0;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
		q.emplace(0, s);
		while (!q.empty()) {
			int e, v;
			tie(e, v) = q.top();
			q.pop();
			if (e > cost[w][v])
				continue;
			for (auto j = g[v].begin(); j != g[v].end(); ++j) {
				bool updated = false;
				if (cost[w][j->first] > e + j->second) {
					cost[w][j->first] = e + j->second;
					updated = true;
				}
				if (cost[w][j->first] > cost[w+1][v] + j->second/2) {
					cost[w][j->first] = cost[w+1][v] + j->second/2;
					updated = true;
				}
				if (updated) {
					q.emplace(cost[w][j->first], j->first);
				}
			}
		}
	}
	return cost[0][d];
}

void solve_stdio()
{
	while (true) {
		int c, n, m, s, d;
		if (!(cin >> c >> n >> m >> s >> d))
			break;
		if (c == 0)
			break;
		s--; d--;
		edges_t edges;
		for (int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			a--; b--;
			edges.emplace_back(a, b, f);
		}
		int ans = solve(c, n, s, d, edges);
		cout << ans << endl;
	}
}

int main()
{
	solve_stdio();
}
