#include<bits/stdc++.h>
using namespace std;

struct Node{
    int townNum, fare, ticketNum;
    bool operator<(const Node &obj)const{
        if(fare != obj.fare)return fare > obj.fare;
        return false;
    }
};

int mini[100][11];

int main(){
    while(1){
        int c,n,m,s,d;
        scanf("%d %d %d %d %d",&c,&n,&m,&s,&d);
        if(c == 0 && n == 0 && m == 0 && s == 0 && d == 0)break;
        vector< vector<Node> > graph;
        graph.resize(n+1);

        for(int i=0;i<m;++i){
            int a,b,f;
            scanf("%d %d %d",&a,&b,&f);
            graph[a].push_back((Node){b,f,0});
            graph[b].push_back((Node){a,f,0});
        }

        for(int i=0;i<n;++i){
            for(int j=0;j<=c;++j){
                mini[i][j] = INT_MAX;
            }
        }
        mini[s-1][c] = 0;

        priority_queue<Node> Q;
        Q.push((Node){s,0,c});
        while(!Q.empty()){
            Node now = Q.top();
            Q.pop();
            if(now.townNum == d){
                cout << now.fare << endl;
                break;
            }
            for(int i=0;i<graph[now.townNum].size();++i){
                Node nextTown = graph[now.townNum][i];
                int newfare=now.fare+nextTown.fare;
                if(newfare < mini[nextTown.townNum-1][now.ticketNum]){
                    Q.push((Node){nextTown.townNum,newfare,now.ticketNum});
                    mini[nextTown.townNum-1][now.ticketNum] = newfare;
                }
                if(now.ticketNum > 0){
                    newfare = now.fare + nextTown.fare / 2;
                    if(newfare < mini[nextTown.townNum-1][now.ticketNum-1]){
                        Q.push((Node){nextTown.townNum,newfare,now.ticketNum-1});
                        mini[nextTown.townNum-1][now.ticketNum-1] = newfare;
                    }
                }
            }
        }
    }

    return 0;
}
