# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <numeric>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 10007;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);

typedef std::pair<int, int> P;
typedef pair<int, P> pp;

const int smax = 100100;

vector<P> edge[smax];
int c, n, m, s, d; // c...??????????????° n...?????? m...??? s...????????? d...?????? 
LL v[15][smax]; //15....max of tickets

int solve() {
	v[c][s] = 0; //?????????
	priority_queue<pp, vector<pp>, greater<pp> > q;
	q.push(pp(0, P(s, c))); //cost,now,ticket(now)
	while (!q.empty()) {
		pp V = q.top();
		q.pop();
		int now_v = V.second.first;
		int now_t = V.second.second;
		if (v[now_t][now_v] < V.first) continue; //v.first(?????????)???v[now_t][now_v]???????????§????????£???????????????????????§?????????

												 //not use tickets
		for (int i = 0; i<edge[now_v].size(); i++) {
			if (v[now_t][edge[now_v][i].first] > v[now_t][now_v] + edge[now_v][i].second) {
				v[now_t][edge[now_v][i].first] = v[now_t][now_v] + edge[now_v][i].second;
				q.push(pp(v[now_t][now_v] + edge[now_v][i].second, P(edge[now_v][i].first, now_t)));
			}
		}

		// use tickets
		if (now_v > 0) {
			for (int i = 0; i<edge[now_v].size(); i++) {
				P p = edge[now_v][i];
				int next_c = p.second / 2;
				if (now_t == 0)continue;
				if (v[now_t - 1][p.first] > v[now_t][now_v] + next_c) {
					v[now_t - 1][p.first] = v[now_t][now_v] + next_c;
					q.push(pp(v[now_t - 1][p.first], P(p.first, now_t - 1)));
				}
			}
		}
	}
	LL ans = INF;
	for (int i = 0; i<c + 1; i++) {
		ans = min(ans, v[i][d]);
	}
	return ans;
}

int main(void) {
	while (cin >> c >> n >> m >> s >> d && c | n | m | s | d) {
		for (int i= 0; i < smax;i++) edge[i].clear();
		fill(v[0], v[0] + 15 * smax, INF);
		for (int i = 0; i < m;i++) {
			int a, b, f;
			cin >> a >> b >> f;
			edge[a].push_back(P(b, f));
			edge[b].push_back(P(a, f));
		}
		cout << solve() << endl;
	}
	return 0;
}