#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pll> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-9;

int C, N, M, S, D;
vector<pii> g[100];
int d[11][100];

int main() {
	while (cin >> C >> N >> M >> S >> D, C || N || M || S || D) {
		S--; D--;
		REP(i, N) g[i].clear();
		
		REP(i, M) {
			int a, b, f;
			scanf("%d %d %d", &a, &b, &f);
			a--; b--;
			g[a].push_back(pii(b, f));
			g[b].push_back(pii(a, f));
		}
		
		fill(d[0], d[11], INF);
		
		priority_queue<pii, vector<pii>, greater<pii> > pq[11];
		
		pq[0].push(pii(0, S));
		d[0][S] = 0;
		
		REP(i, C + 1) {
			while (!pq[i].empty()) {
				pii now = pq[i].top(); pq[i].pop();
				int u = now.se, cost = now.fi;
				REP(i, g[u].size()) {
					int v = g[u][i].fi, c = g[u][i].se;
					if (i < C && chmin(d[i + 1][v], cost + c / 2)) pq[i + 1].push(pii(cost + c / 2, v));
					if (chmin(d[i][v], cost + c)) pq[i].push(pii(cost + c, v));
				}
			}
		}
		
		int ans = INF;
		REP(i, C + 1) chmin(ans, d[i][D]);
		cout << ans << endl;
	}
	return 0;
}