#include <iostream>
#include <queue>
#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)

struct edge {
    int to,cost;
};
struct state {
    int v,d;
    bool operator<(const state& s) const {
        return d>s.d;
    }
};

vector<vector<edge>> G;
array<array<int,11>,101> dp;
priority_queue<state> q;
int c,n,m,s,d;

int main(){
    while(cin>>c>>n>>m>>s>>d, c||n||m||s||d){
        G=vector<vector<edge>>(n+1);
        rep(i,m){
            int f,t,c; cin>>f>>t>>c;
            G[f].push_back({t,c});
            G[t].push_back({f,c});
        }
        rep(i,c+1){
            dp[i].fill(1<<30);
            dp[i][s]=0;
            priority_queue<state>().swap(q);
            q.push({s,0});
            while(q.size()){
                state sta=q.top(); q.pop();
                if(dp[i][sta.v]<sta.d) continue;
                for(edge& e:G[sta.v]){
                    int t;
                    if(i==0) t=dp[0][sta.v]+e.cost;
                    else t=min(dp[i][sta.v]+e.cost,
                               dp[i-1][sta.v]+e.cost/2);
                    if(dp[i][e.to]>t){
                        dp[i][e.to]=t;
                        q.push({e.to,t});
                    }
                }
            }
        }
        cout<<dp[c][d]<<endl;
    }
}