#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))

typedef long long int ll;

using namespace std;

int c,n,m,s,d;

int main(){
    while(true){
	scanf("%d%d%d%d%d",&c,&n,&m,&s,&d);
	if(c==0||n==0||m==0||s==0||d==0) break;
	int rosen[101][101] = {10000000};
	int dp[11][101];
	REP(i,101)REP(j,101) rosen[i][j] = 10000000;
	REP(i,11)REP(j,101) dp[i][j] = 10000000;
	REP(i,m){
	    int a,b,f;
	    cin >> a >> b >> f;
	    rosen[a][b] = f;
	    rosen[b][a] = f;
	}
	int ans = 10000000;
	vector<bool>  used(n+1,false);
	queue<int> q;
	queue<int> th;
	dp[c][s] = 0;
	q.push(s);
	th.push(c);
	while(!q.empty()){
	    int p = q.front();
	    int t = th.front();
	    q.pop();
	    th.pop();
	    FOR(i,1,n+1){
		if(dp[t][i] > dp[t][p] + rosen[p][i]){
		    dp[t][i] = dp[t][p] + rosen[p][i];
		    q.push(i);
		    th.push(t);
		}
		if(t>0&&dp[t-1][i] > dp[t][p] + rosen[p][i]/2){
		    dp[t-1][i] = dp[t][p] + rosen[p][i]/2;
		    q.push(i);
		    th.push(t-1);
		}
	    }
	}
	REP(i,c+1){
	    if(dp[i][d] > 0)
		ans = min(ans,dp[i][d]);
	}
	cout << ans << endl;
    }
    return 0;
}