#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0212

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX_VAL 110
#define MAX_C 12

typedef long long ll;
typedef pair<pair<ll,ll>,int> P;

struct edge{ll to, cost;};


int dijkstra(vector<edge> G[MAX_VAL], int s, int g, int V, int c){
	priority_queue<P,vector<P>,greater<P>> q;
	ll d[MAX_C][MAX_VAL];
	
	for(int i = 0; i < MAX_C; i++) for(int j = 0; j < MAX_VAL; j++) d[i][j] = INF;
	
	d[0][s] = 0;
	q.push(P(make_pair(0,s),0));
	
	while(!q.empty()){
		P p = q.top();q.pop();
		ll v = p.first.second;
		
		if(v == g) return d[p.second][v];
		
		if(d[p.second][v] < p.first.first) continue;
		
		for(edge e : G[v]){
			if(d[p.second][e.to] > d[p.second][v] + e.cost){
				d[p.second][e.to] = d[p.second][v] + e.cost;
				q.push(P(make_pair(d[p.second][e.to],e.to),p.second));
			}
			if(c > p.second && d[p.second+1][e.to] > d[p.second][v] + e.cost/2){
				d[p.second+1][e.to] = d[p.second][v] + e.cost/2;
				q.push(P(make_pair(d[p.second+1][e.to],e.to),p.second+1));
			}
		}
	}
	
	// int res = INF;
	
	// for(int i = 0; i <= c; i++){
		// res = min(res,d[i][g]);
	// }
	// return res;
}

signed main(){
	// cin.tie(0);
	// ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int c, n, m, s, d;
	int a, b, f;
	edge temp;
	
	
	while(true){
		vector<edge> G[MAX_VAL];
		
		cin>>c>>n>>m>>s>>d;
		
		if(!c&&!n&&!m&&!s&&!d) break;
		
		for(int i = 0; i < m; i++){
			cin>>a>>b>>f;
			temp.cost = f, temp.to = b;
			G[a].push_back(temp);
			temp.to = a;
			G[b].push_back(temp);
		}
		
		cout<<dijkstra(G,s,d,n,c)<<endl;
	}
	
	return 0;
}
