#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;

struct state{
	int pos;
	int ticket;
	int sum;
	
	bool operator< (const state &s) const{
		return s.sum < sum;
	}
};

struct edge{
	int to;
	int fee;
};

int c, n, m, s, d;
vector<vector<edge> > G;

int solve(){
	vector<vector<int> > v(n + 1, vector<int>(c + 1, 1000000000));

	priority_queue<state> pq;
	pq.push((state){s, c, 0});
	v[s][c] = 0;

	while(!pq.empty()){
		state st = pq.top();
		pq.pop();

		if(v[st.pos][st.ticket] != st.sum){ continue; }
		if(st.pos == d) return st.sum;

		for(int i = 0; i < G[st.pos].size(); ++i){
			int t = G[st.pos][i].to;
			int f = G[st.pos][i].fee + st.sum;
			if(v[t][st.ticket] > f){
				v[t][st.ticket] = f;
				pq.push((state){t, st.ticket, f});
			}
			
			if(st.ticket > 0){
				f = G[st.pos][i].fee / 2 + st.sum;
				if(v[t][st.ticket - 1] > f){
					v[t][st.ticket - 1] = f;
					pq.push((state){t, st.ticket - 1, f});
				}
			}
		}
	}
	return -1;
}

int main(){
	int a, b, f;
	while(scanf("%d%d%d%d%d", &c, &n, &m, &s, &d), n){
		G.assign(n + 1, vector<edge>());
		for(int i = 0; i < m; ++i){
			scanf("%d%d%d", &a, &b, &f);
			G[a].push_back((edge){b, f});
			G[b].push_back((edge){a, f});
		}
		
		printf("%d\n", solve());
	}
}