#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <numeric>
#include <limits>

using namespace std;

struct edge{ int to, cost; };
typedef pair<int, int> P;
const int INF = INT_MAX / 4;

int V;
vector<edge> G[100];
int D[100];
int pre[100];

int c, n, m, s, d;

void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	fill(D, D + 100, INF);
	fill(pre, pre + 100, -1);
	D[s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (D[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); i++)
		{
			edge e = G[v][i];
			if(D[e.to] > D[v] + e.cost)
			{
				D[e.to] = D[v] + e.cost;
				pre[e.to] = v;
				que.push(P(D[e.to], e.to));
			}
		}
	}
}

int solve()
{
	dijkstra(s - 1);
	vector<int> vec;
	for (int t = d - 1; pre[t] != -1 ; t = pre[t])
	{
		for (int i = 0; i < G[t].size(); i++)
		{
			if(pre[t] == G[t][i].to)
			{
				vec.push_back(G[t][i].cost);
				break;
			}
		}
	}
	sort(vec.begin(), vec.end(), greater<int>());
	for (int i = 0; i < c && i < vec.size(); i++)
	{
		vec[i] = vec[i] / 2;
	}
	return accumulate(vec.begin(), vec.end(), 0);
}

int main()
{
	while (cin >> c >> n >> m >> s >> d && c && n && m && s && d)
	{
		for (int i = 0; i < 100; i++)
		{
			G[i] = vector<edge>();
		}
		for (int i = 0; i < m; i++)
		{
			int a, b, f;
			cin >> a >> b >> f;
			edge e;
			e.to = b - 1;
			e.cost = f;
			G[a - 1].push_back(e);
			e.to = a - 1;
			e.cost = f;
			G[b - 1].push_back(e);
		}
		cout << solve() << endl;
	}
	return 0;
}