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

typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int dijkstra(int s, int g, int c, vector<vector<P>> &G){
    vector<vector<int>> dist(110, vector<int>(20, 1e9));
    priority_queue<T, vector<T>, greater<T>> que;
    dist[s][0] = 0;
    que.emplace(0, s, 0);

    while(!que.empty()){
        int ccost, cv, cused;
        tie(ccost, cv, cused) = que.top();
        que.pop();

        if(dist[cv][cused] < ccost) continue;

        for(auto x : G[cv]){
            int nv, ncost;
            tie(nv, ncost) = x;

            if(dist[cv][cused] + ncost < dist[nv][cused]){
                dist[nv][cused] = dist[cv][cused] + ncost;
                que.emplace(dist[nv][cused], nv, cused);
            }

            if(cused < c){
                if(dist[cv][cused] + ncost / 2 < dist[nv][cused+1]){
                    dist[nv][cused+1] = dist[cv][cused] + ncost / 2;
                    que.emplace(dist[nv][cused+1], nv, cused + 1);
                }
            }
        }
    }

    int ans = 1e9;
    for(int i=0; i<=c; i++){
        ans = min(ans, dist[g][i]);
    }

    return ans;
}

int main(){
    while(1){
        int c, n, m, s, d; cin>>c>>n>>m>>s>>d;
        s--, d--;
        if(c == 0) return 0;

        vector<vector<P>> G(n);
        for(int i=0; i<m; i++){
            int a, b, f; cin>>a>>b>>f;
            a--, b--;
            G[a].emplace_back(b, f);
            G[b].emplace_back(a, f);
        }

        cout << dijkstra(s, d, c, G) << endl;
    }
}
