#include <iostream>
#include <array>
#include <vector>

using namespace std;
#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)
#define eacha(e,c) for(auto &e:c)

struct edge {
    int from,to,cost;
};

vector<edge> E;
array<array<int,11>,101> dp;
int c,n,m,s,d;

int main(){
    while(cin>>c>>n>>m>>s>>d, c|n|m|s|d){
        vector<edge>(m*2).swap(E);
        rep(i,m) cin>>E[i].from>>E[i].to>>E[i].cost;
        rep(i,c+1){
            dp[i].fill(1<<30);
            dp[i][s]=0;
            bool end;
            while(1){
                end=1;
                eacha(e,E){
                    rep(a,2){
                        int nd;
                        if(i==0) nd=dp[i][e.from]+e.cost;
                        else nd=min(dp[i-1][e.from]+e.cost/2,
                                    dp[i][e.from]+e.cost);
                        if(nd<dp[i][e.to]){
                            dp[i][e.to]=nd;
                            end=false;
                        }
                        swap(e.to,e.from);
                    }
                }
                if(end) break;
            }
        }
        cout<<dp[c][d]<<endl;
    }
}