#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <map>

using namespace std;

struct node
{
	int ticket, si;
	int cost;
	bool det;
};

struct comparator : public binary_function<node *, node *, bool>
{
	bool operator() (node *x, node *y) const { return x->cost > y->cost; }
};

typedef pair<int, int> edge_t;
typedef list<edge_t> edgelist_t;

static node nodes[11][101];
static map<int, edgelist_t > edges;

int main()
{
	int C,N,M,S,D;
	while(cin>>C>>N>>M>>S>>D, C&&N&&S&&M&&D)
	{
		for (int c = 0; c <= C; c++)
		{
			for (int i = 1; i <= N; i++)
			{
				nodes[c][i].ticket = c;
				nodes[c][i].si = i;
				nodes[c][i].cost = 1 << 16;
				nodes[c][i].det = false;
			}
		}

		edges.clear();
		for (int i = 0; i < M; i++)
		{
			int a,b,f;
			cin>>a>>b>>f;
			edges[a].push_back(make_pair(b, f));
			edges[b].push_back(make_pair(a, f));
		}

		// Dijkstra
		priority_queue<node *, vector<node *>, comparator> queue;
		nodes[C][S].cost = 0;
		queue.push(&nodes[C][S]);

		int min_cost = 1 << 16;
		while (!queue.empty())
		{
			node *n = queue.top();
			queue.pop();
			if (n->det) continue;
			n->det = true;

			if (n->si == D) min_cost = min(min_cost, n->cost);

			edgelist_t &l = edges[n->si];
			edgelist_t::const_iterator it;
			for (it = l.begin(); it != l.end(); ++it)
			{
				node *n2 = &nodes[n->ticket][(*it).first];
				int cost = (*it).second;

				if (!n2->det)
				{
					n2->cost = min(n2->cost, n->cost + cost);
					queue.push(n2);
				}
				if (n->ticket > 0)
				{
					n2 = &nodes[n->ticket - 1][(*it).first];
					cost = (*it).second / 2;
					if (!n2->det)
					{
						n2->cost = min(n2->cost, n->cost + cost);
						queue.push(n2);
					}
				}
			}
		}
		cout << min_cost << endl;
	}
	return 0;
}