#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 rosen[101][101] = {-1};
int saiki(int p,vector<int> st,vector<bool> &u){
    int ans = INF;
    if(p == d){
	sort(RALL(st));
	int tc = min(c,(int)(st.size()));
	REP(i,tc){
	    st[i] /= 2;
	}
	int sum = 0;
	REP(i,st.size()){
	    sum += st[i];
	}
	return sum;
    }
    FOR(i,1,n+1){
	if(!u[i] && rosen[p][i] > 0){
	    vector<int> temp = st;
	    vector<bool> utemp = u;
	    temp.PB(rosen[p][i]);
	    utemp[i] = true;
	    ans = min(ans,saiki(i,temp,utemp));
	}
    }
    return ans;
}

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;
	memset(rosen,-1,sizeof(rosen));
	REP(i,m){
	    int a,b,f;
	    cin >> a >> b >> f;
	    rosen[a][b] = f;
	    rosen[b][a] = f;
	}
	vector<bool>  used(n+1,false);
	vector<int> nanika;
	used[s] = true;
	cout << saiki(s, nanika ,used) << endl;
    }
    return 0;
}