#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const int inf = 1000001;

class St{
	public:
	int c, p, cost;
	St() {}
	St(int _c, int _p, int _cost): c(_c), p(_p), cost(_cost) {}
	
	bool operator>(const St& st) const{
		return cost > st.cost;
	}
};

int exdij(int a[101][101], int c, int n, int s, int t)
{
	int r = inf, mcost[101][11];
	bool vis[101][11];
	priority_queue<St, vector<St>, greater<St> > que;
	
	que.push(St(c, s, 0));
	fill(&vis[0][0], &vis[100][10], true);
	fill(&mcost[0][0], &mcost[100][10], inf);
	while(!que.empty()){
		St st = que.top();
		que.pop();
		if(st.p == t){
			r = st.cost;
			break;
		}
		if(!vis[st.p][st.c]){
			continue;
		}
		vis[st.p][st.c] = false;
		
		for(int i = 1; i <= n; i++){
			if(mcost[i][st.c] > st.cost+a[st.p][i]){
				mcost[i][st.c] = st.cost+a[st.p][i];
				que.push(St(st.c, i, mcost[i][st.c]));
			}
			if(st.c && mcost[i][st.c-1] > st.cost+a[st.p][i]/2){
				mcost[i][st.c-1] = st.cost+a[st.p][i]/2;
				que.push(St(st.c-1, i, mcost[i][st.c-1]));
			}
		}
	}
	
	return r;
}

int main()
{
	int c, n, m, s, d, t, u, f, a[101][101];
	
	while(cin>>c>>n>>m>>s>>d && (c+n+m+s+d)){
		fill(&a[0][0], &a[n][n], inf);
		for(int i = 0; i <= n; i++){
			a[i][i] = 0;
		}
		while(m--){
			cin >> t >> u >> f;
			a[t][u] = a[u][t] = f;
		}
		
		cout << exdij(a, c, n, s, d) << endl;
	}
	
	return 0;
}