#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
const ll INF = 114514810;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int V;
int d[2000];
vector<vector<edge>> es;

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

int main()
{
	int c, n, m, s, g;
	while (cin >> c >> n >> m >> s >> g, c)
	{
		V = n;
		s--; g--;
		es.clear();
		es.resize(c*n+n);
		REP(i, n)
		{
			int a, b, f;
			cin >> a >> b >> f;
			a--; b--;
			REP(j, c+1) es[a + j*n].push_back(edge{ a + j*n, b + j*n, f });
			REP(j, c) es[a + (j+1)*n].push_back(edge{ a + (j+1)*n, b + j*n, f/2 });
			REP(j, c + 1) es[b + j*n].push_back(edge{ b + j*n, a + j*n, f });
			REP(j, c) es[b + (j + 1)*n].push_back(edge{ b + (j + 1)*n, a + j*n, f / 2 });
		}
		dijkstra(s + c*n);
		int ans = INF;
		REP(i, c + 1) ans = min(ans, d[g + i*n]);
		cout << ans << endl;
	}

	return 0;
}