#include <iostream>
#include <queue>
//#include <fstream>	// require freopen

using namespace std;

const int MAX_N = 100;
const int INF = 10000000;
const int MAX_C = 10;

// XÌîñ
// pair <cèÌø, XÌÔ>
typedef pair<int, int > T;

// n_Ìîñ
// pair <Å¬RXg,n_Ìîñ>
typedef pair<int, T > P;

// üÍ
int c, n, m, s, d;

// »ÌXÜÅÌÅ¬ÌRXg
// cost[cèÌø][XÌÔ] = ïp
int cost[MAX_C + 1][MAX_N];

// ùÉÅKlªèÏÝ©Ç¤©
bool flag[MAX_C + 1][MAX_N];

// HüÌîñ
// line[n_][I_] = ¿à
int line[MAX_N][MAX_N];

// DPpÌL[
typedef priority_queue <P, vector <P>, greater<P> > Q;
Q dp_q;

// _CNXg@
int dijkstra ()
{
	while (!dp_q.empty() ){
		P p = dp_q.top(); dp_q.pop();
		T &t = p.second;

		// ùÉÅKlªèÏÝ©²×é
		if (flag[t.first][t.second] ){
			continue;
		} // end if
		
		flag[t.first][t.second] = true;

		// ÅIn_
		if (t.second == d ){
			return p.first;
		} // end if

		for (int i = 0; i < n; ++i ){
			// øðgíÈ¢ê
			if (cost[t.first][i] > p.first + line[t.second][i] ){
				cost[t.first][i] = p.first + line[t.second][i];
				dp_q.push (P(p.first + line[t.second][i], T(t.first, i ) ) );
			} // end if

			// øðg¤ê
			if (t.first > 0 && cost[t.first - 1][i] > p.first + line[t.second][i]/2 ){
				cost[t.first - 1][i] = p.first + line[t.second][i]/2;
				dp_q.push (P(p.first + line[t.second][i]/2, T(t.first - 1, i ) ) );
			} // end if
		} // end for
	} // end while

	return INF;
}

void solve()
{
	// ú»
	for (int i = 0; i <= MAX_C; ++i ){
	 	for (int j = 0; j < MAX_N; ++j ){
			cost[i][j] = INF;
			flag[i][j] = false;
		} // end for
	} // end for

	// Jnn_
	dp_q = Q();
	dp_q.push (P(0, T(c, s ) ) );

	// _CNXg@
	int res = dijkstra();

	cout << res << endl;
}

int main()
{
//	cut here before submit 
//	freopen ("testcase.heb", "r", stdin );

	while (cin >> c >> n >> m >> s >> d && c && n && m && s && d){
		s--;d--;
		for (int i = 0; i < MAX_N; ++i ){
			for (int j = 0; j < MAX_N; ++j ){
				line[i][j] = INF;
			} // end for
		} // end for

		for (int i = 0; i < m; ++i ){
			int a, b, f;
			cin >> a >> b >> f;
			a--; b--;
			line[a][b] = f; line[b][a] = f;
		} // end for

		solve();
	} // end while

	return 0;
}