#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <istream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <climits>
using namespace std;

typedef ostringstream OSS;
typedef istringstream ISS;

typedef vector<int> VI;
typedef vector< VI > VVI;

typedef long long LL;

typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define X first
#define Y second

typedef pair<int, pair<int, int>> STATE;

const int INF = INT_MAX / 4;

int main(void) {
	int c, n, m, s, d;

	while (cin >> c >> n >> m >> s >> d, c) {
		s--; d--;

		VVI es(n, VI(n, INF));
		for (int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			es[a - 1][b - 1] = f;
			es[b - 1][a - 1] = f;
		}

		VVI distance(n, VI(c + 1, INF));	// node, ticket
		distance[s][c] = 0;
		priority_queue<STATE, vector<STATE>, greater<STATE>> q; // cost, node, ticket
		q.push(STATE(0, make_pair(s, c)));

		while (q.size()) {
			int cost = q.top().first;
			int node = q.top().second.first;
			int ticket = q.top().second.second;
			q.pop();

			if (cost > distance[node][ticket]) {
				continue;
			}

			for (int i = 0; i < n; i++) if (es[node][i] != INF) {
				int next_cost;

				// not use ticket
				next_cost = distance[node][ticket] + es[node][i];
				if (distance[i][ticket] > next_cost) {
					distance[i][ticket] = next_cost;
					q.push(STATE(next_cost, make_pair(i, ticket)));
				}

				// ticket - 1
				if (ticket) {
					next_cost = distance[node][ticket] + es[node][i] / 2;
					if (distance[i][ticket - 1] > next_cost) {
						distance[i][ticket - 1] = next_cost;
						q.push(STATE(next_cost, make_pair(i, ticket - 1)));
					}
				}
			}
		}

		cout << *min_element(distance[d].begin(), distance[d].end()) << endl;
	}

	return 0;
}