#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype

template <class T>
int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount

const double EPS = 1e-8;
typedef long long ll;
typedef pair<int, int> pint;

typedef pair<int, pint> P;

int dp[101][11];

int main()
{
	int c, n, m, s, d;
	while (scanf("%d%d%d%d%d", &c, &n, &m, &s, &d), c|n|m|s|d)
	{
		vector<pint> edge[101];
		for (int i = 0; i < m; ++i)
		{
			int a, b, f;
			scanf("%d%d%d", &a, &b, &f);
			edge[a].push_back(pint(b, f));
			edge[b].push_back(pint(a, f));
		}

		const int INF = 2 << 25;
		for (int i = 1; i <= n; ++i)
			for (int j = 0; j <= c; ++j)
				dp[i][j] = INF;

		priority_queue<P, vector<P>, greater<P> > q;
		q.push(P(0, pint(s, c)));
		while (!q.empty())
		{
			P e = q.top();
			q.pop();
			int cost = e.first;
			int from = e.second.first;
			int ticket = e.second.second;

			if (cost >= dp[from][ticket])
				continue;
			dp[from][ticket] = cost;

			foreach (it, edge[from])
			{
				int to = it->first;
				int f = it->second;
				q.push(P(cost + f, pint(to, ticket)));
				if (ticket)
					q.push(P(cost + f/2, pint(to, ticket-1)));
			}
		}

		printf("%d\n", *min_element(dp[d], dp[d]+c+1));
	}

	return 0;
}