#include <cstdio>
#include <queue>
#include <algorithm>

#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

const int inf = 2e7;

typedef pair<int, int> P;

struct E{
	E(int t, int c) :
		t(t), c(c)
	{}

	int t, c;
};

int c, n, m, s, t;
vector<E> g[1100];
int d[1100];

int index(int i, int j){
	return i * (c + 1) + j;
}

int main(){
	while(1){
		scanf("%d%d%d%d%d", &c, &n, &m, &s, &t);
		--s;
		--t;
		if(c == 0){
			break;
		}
		rep(i, m){
			int a, b, k;
			scanf("%d%d%d", &a, &b, &k);
			--a;
			--b;
			rep(j, c + 1){
				g[index(a, j)].push_back(E(index(b, j), k));
				g[index(b, j)].push_back(E(index(a, j), k));
			}
			rep(j, c){
				g[index(a, j + 1)].push_back(E(index(b, j), k / 2));
				g[index(b, j + 1)].push_back(E(index(a, j), k / 2));
			}
		}

		fill_n(d, n * (c + 1), inf);

		priority_queue<P, vector<P>, greater<P> > q;
		d[index(s, c)] = 0;
		q.push(P(0, index(s, c)));
		while(!q.empty()){
			P v = q.top();
			q.pop();
			if(v.first > d[v.second]){
				continue;
			}
			rep(i, g[v.second].size()){
				E e = g[v.second][i];
				if(d[e.t] > v.first + e.c){
					d[e.t] = v.first + e.c;
					q.push(P(d[e.t], e.t));
				}
			}
		}

		printf("%d\n", *min_element(d + index(t, 0), d + index(t + 1, 0)));

		rep(i, n * (c + 1)){
			g[i].clear();
		}
	}
	return 0;
}