#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

#define reep(i,n,m) for(int i=(n);i<(m);i++)
#define rep(i,n) reep(i,0,n)

using namespace std;

class Edge{
public:
    int to;
    int cost;
    Edge(int to,int cost):to(to),cost(cost){}
};

class Node{
public:
    int used;
    int p;
    int cost;
    Node(int u,int n,int c):used(u),p(n),cost(c){}

    bool operator<(const Node &a)const{
        return cost>a.cost;
    }
};

int main(){
    int c,n,m,s,d;
    while(cin>>c>>n>>m>>s>>d,c+n+m+s+d){

        vector<Edge> edge[101];
        rep(i,m){
            int a,b,f;
            cin >> a >> b >> f;
            edge[a].push_back(Edge(b,f));
            edge[b].push_back(Edge(a,f));
        }

        priority_queue<Node> Q;
        Q.push(Node(0,s,0));

        bool used[101][11] = {0};

        while(!Q.empty()){
            Node node = Q.top();Q.pop();
            if(used[node.p][node.used]){
                continue;
            }
            used[node.p][node.used] = true;

            int p = node.p;

            if(p==d){
                cout << node.cost << endl;
                break;
            }

            rep(i,edge[p].size()){
                Edge e = edge[p][i];
                int next = e.to;
                int cost = node.cost + e.cost;
                Q.push(Node(node.used,next,cost));
                if(node.used<c){
                    cost = node.cost + e.cost/2;
                    Q.push(Node(node.used+1,next,cost));
                }
            }
        }
    }
    return 0;
}