#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct Edge{
    Edge(){};
    Edge(int _to,int _cost){
        to = _to;
        cost = _cost;
    }
    int to;
    int cost;
};
struct Data{
    Data(){};
    Data(int _pos,int _t, int _ck){
        pos = _pos;
        t = _t;
        ck = _ck;
    }
    int pos;
    int t;
    int ck;
    bool operator < (const Data &a)const{
        return t > a.t;
    }
};
int main(){
    int c,n,m,s,d;
    while(cin>>c>>n>>m>>s>>d,c){
        int vis[120][12];
        vector<Edge> Node[120];
        for(int i = 0;i < m;i++){
            int x,y,t;
            cin>>x>>y>>t;
            Node[x].push_back(Edge(y,t));
            Node[y].push_back(Edge(x,t));
        }
        for(int i = 0;i < 120;i++)for(int j = 0;j < 12;j++)vis[i][j] = 1e+9;
        priority_queue<Data> Q;
        Q.push(Data(s,0,0));
        while(!Q.empty()){
            Data D = Q.top();Q.pop();
            int p = D.pos;
            int k = D.ck;
            if(vis[p][k] < D.t)continue;
            for(int i = 0;i < Node[p].size();i++){
                Edge e = Node[p][i];
                if(vis[e.to][k] > D.t + e.cost){
                    vis[e.to][k] = D.t + e.cost;
                    Q.push(Data(e.to,vis[e.to][k],k));
                }
                if(k < c && vis[e.to][k + 1] > D.t + e.cost/2){
                    vis[e.to][k + 1] = D.t + e.cost/2;
                    Q.push(Data(e.to,vis[e.to][k + 1],k+1));
                }
            }
        }

        int ans = 1e+9;
        for(int i = 0;i <= c;i++){
            ans = min(ans, vis[d][i]);
        }
        cout<<ans<<endl;
    }
}