#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

int C, N, M, S, D; //??????????????°???????????°???????????°???????????°???????????°
int cost[101];
int INF = 999999999;

class Edge
{
public:
	int to, cost;
	Edge(int to, int cost) : to(to), cost(cost){}
};

class Vertax
{
public:
	int n;
	int cost;
	priority_queue<int, vector<int>, greater<int>> discount;
	Vertax(){}

	Vertax get(Edge e)
	{
		Vertax v = *this;
		if (discount.size() == C)
		{
			v.cost += e.cost / 2;
			v.discount.push(e.cost);
			v.cost += discount.top() / 2;
			v.discount.pop();
		}
		else
		{
			v.cost += e.cost / 2;
			v.discount.push(e.cost);
		}
		v.n = e.to;
		return v;
	}
};

bool operator > (Vertax v1, Vertax v2)
{
	return (v1.cost > v2.cost);
}
bool operator < (Vertax v1, Vertax v2)
{
	return (v1.cost < v2.cost);
}

priority_queue<Vertax, vector<Vertax>, greater<Vertax>> que;

int main()
{
	while (cin >> C >> N >> M >> S >> D, C + N + M + S + D)
	{
		fill(cost + 1, cost + N + 1, INF);
		vector<Edge> e[501];

		for (int i = 0; i < M; i++)
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			e[from].push_back(Edge(to, cost));
			e[to].push_back(Edge(from, cost));
		}

		Vertax start;
		start.n = S;
		start.cost = 0;
		que.push(start);
		cost[S] = 0;

		while (!que.empty())
		{
			Vertax v = que.top();
			que.pop();

			for (int i = 0; i < e[v.n].size(); i++)
			{
				Edge edge = e[v.n][i];
				Vertax next = v.get(edge);
				if (cost[next.n] > next.cost)
				{
					cost[next.n] = next.cost;
					que.push(next);
				}
			}
		}

		cout << cost[D] << endl;
	}

	return 0;
}