#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;


// Highway Express Bus
// input 
// c n m s d : ????????? ????????° ???????????° ????????°??? ????????°???
// a b f : a??????b?????§f???

#define INF 1e+9
typedef pair<int, int> P;
struct edge{
	int to, cost; 
};

int c, n, m, s, d;
vector<edge> G[101];
int dp[11][101];	//????????????i???????????????j??°????????§???????°??????????


void dijkstra(int s,int a){		//????????????????????????????????°???a???????????????????????????
    priority_queue<P, vector<P>, greater<P> >Q;	//greater: ????´?????°????????????§??????????????¨????????????
    for(int i=0 ;i<n; i++) dp[a][i] = INF;
    dp[a][s] = 0;
    Q.push(P(0,s));	//??????????????°???
    
    while(!Q.empty()){
        P p=Q.top();  //p<cost, vertex>
        Q.pop();
        int v = p.second;
        
        if(dp[a][v] < p.first)continue;
        for(int i=0; i<G[v].size(); i++){
            edge e = G[v][i];	//v?????????????????´????????????{??°???????????????}
            int dm;
            if(a==0) dm = dp[a][v] + e.cost;	//???????????????????????¨???
            else dm = min(dp[a][v] + e.cost, dp[a-1][v] + e.cost/2);	//v?????????????????´?????§??????????????????
            															//??????????????§???????°????

            if(dp[a][e.to] > dm){
                dp[a][e.to] = dm;	//dm????????????????????????????????´??°
                Q.push(P(dp[a][e.to],e.to));	//?????\??????(?????????,?¬???°???)??§??\??????
            }
        }
    }
}


int main(){

	while(1){
		cin >> c >> n >> m >> s >> d;
		s--;
		d--;
		if(c==0) break;

		for(int i=0 ; i<m ; i++){
			int a, b, f;
			cin >> a >> b >> f;

			a--;
			b--;

			G[a].push_back((edge){b,f});	//??£??\?????????:a??????b?????§????????????
			G[b].push_back((edge){a,f});
		}

		int ans = INF;
	    for(int i=0;i<=c;i++){
    		dijkstra(s,i);
		}
        
	    cout << dp[c][d] << endl;
	     
	    for(int i=0;i<100;i++)G[i].clear();
	}

	return 0;
}