#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

struct Edge {
	int to;
	int ticket;
	int cost;
	Edge(int to, int cost, int ticket) : to(to), cost(cost), ticket(ticket) {}
	Edge() {}
};

bool operator < (const Edge &a, const Edge &b)
{
	return (a.cost > b.cost);
}

int main()
{
	int c, n, m, s, d;
	
	while (scanf("%d %d %d %d %d", &c, &n, &m, &s, &d) && c){
		
		vector<Edge> graph[128];
		
		for (int i = 0; i < m; i++){
			int f, t, cost;
			scanf("%d %d %d", &f, &t, &cost);
			graph[--f].push_back(Edge(--t, cost, 0));
			graph[t].push_back(Edge(f, cost, 0));
		}
		
		bool done[16][128];
		memset(done, false, sizeof(done));
		
		priority_queue<Edge> pq;
		
		pq.push(Edge(s - 1, 0, 0));
		
		int ans = -1;
		while (!pq.empty()){
			Edge t = pq.top(); pq.pop();
			
			if (done[t.ticket][t.to]) continue;
			done[t.ticket][t.to] = true;
			
			if (t.to == d - 1){
				if (~ans) ans = min(ans, t.cost);
				else ans = t.cost;
			}
			
			int v = t.to;
			for (int i = 0; i < graph[v].size(); i++){
				pq.push(Edge(graph[v][i].to, t.cost + graph[v][i].cost, t.ticket));
				if (t.ticket < c){
					pq.push(Edge(graph[v][i].to, t.cost + graph[v][i].cost / 2, t.ticket + 1));
				}
			}
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}