#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define RPA(i,s,e) for(int i=s; i<=e; i++)
#define RPD(i,s,e) for(int i=s; i>=e; i--)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cout << (a) << endl

typedef pair<int,int> P;

struct edge { int to, cost; };

const int INF = 1000000009;
const int MAX_V = 111;
const int MAX_C = 15;
vector<edge> G[MAX_V];

int c, n, m, s, d;
int p, q, r;
int dp[MAX_C][MAX_V];

void add_edge(int from, int to, int cost) {
	edge e1 = { to, cost };
	edge e2 = { from, cost };
	G[from].PB(e1);
	G[to].PB(e2);
}

void dijkstra(int f, int t, int k) {
	REP(j,n) dp[k][j] = INF;

	priority_queue<P, vector<P>, greater<P> > que;
	que.push(MP(0, f));
	dp[k][f] = 0;

	while(!que.empty()) {
		P p = que.top();
		que.pop();

		int v = p.second;
		REP(i,G[v].size()) {
			edge& e = G[v][i];
			int minval = dp[k][v] + e.cost;
			if(k > 0) minval = min(minval, dp[k-1][v] + e.cost / 2);
			if(dp[k][e.to] > minval) {
				dp[k][e.to] = minval;
				que.push(P(minval, e.to));
			}
		}
	}
}

void solve() {
	RPA(i,0,c) {
		dijkstra(s, d, i);
	}
	PRT(dp[c][d]);
}

void coding() {
	while(scanf("%d%d%d%d%d", &c, &n, &m, &s, &d) != EOF) {
		if(c == 0 && n == 0 && m == 0 && s == 0 && d == 0) break;

		s--; d--;
		REP(i,n) G[i].clear();

		REP(i,m) {
			scanf("%d%d%d", &p, &q, &r);
			p--; q--;
			add_edge(p, q, r);
		}
		solve();
	}
}

//#define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
	freopen("a.in", "r", stdin);
#endif

	coding();

#ifdef _LOCAL_TEST
	cout << endl;
	cout << "This is local test" << endl;
	cout << "Do not forget to comment out _LOCAL_TEST" << endl;
#endif
}