#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct Edge{
    int to,cost;
};
struct data{
    int nowp,sumcost,tic;
    data(){}
    data(int _nowp,int _sumcost,int _tic){
        nowp=_nowp,sumcost=_sumcost,tic=_tic;
    }
    bool operator<(const data &a)const{
        return sumcost>a.sumcost;
    }
};
const int INF=100000000;
int main(){
    while(1){
        int c,n,m,s,g;
        vector<Edge> edge[102];
        scanf("%d %d %d %d %d",&c,&n,&m,&s,&g);
        if(c==0&&n==0&&m==0&&s==0&&g==0)
            break;
        for(int i=0;i<m;i++){
            int be,af,co;
            scanf("%d %d %d",&be,&af,&co);
            Edge a;
            a.to=af,a.cost=co;
            edge[be].push_back(a);
            a.to=be;
            edge[af].push_back(a);
        }
        int coslis[11][102];
        fill(coslis[0],coslis[0]+11*102,INF);
        priority_queue<data> que;
        que.push(data(s,0,c));
        while(!que.empty()){
            data nowrig=que.top(); que.pop();
            //printf(" %d,%d,%d\n",nowrig.nowp,nowrig.sumcost,nowrig.tic);
            if(coslis[nowrig.tic][nowrig.nowp]!=INF)
                continue;
            coslis[nowrig.tic][nowrig.nowp]=nowrig.sumcost;
            for(int i=0;i<edge[nowrig.nowp].size();i++){
                data a;
                a.nowp=edge[nowrig.nowp][i].to;
                a.sumcost=nowrig.sumcost+edge[nowrig.nowp][i].cost;
                a.tic=nowrig.tic;
                que.push(a);
                if(0<nowrig.tic){
                    a.sumcost=nowrig.sumcost+(edge[nowrig.nowp][i].cost/2);
                    a.tic=nowrig.tic-1;
                    que.push(a);
                }
            }
        }
        int ans=INF;
        for(int i=0;i<=10;i++)
            ans=min(ans,coslis[i][g]);
        printf("%d\n",ans);
    }
    return 0;
}