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

constexpr int INF = 1e9;

struct edge {
    int to, cost;
};

using edges = vector<edge>;
using graph = vector<edges>;

int main() {
    int C, N, M, S, D;
    while(cin >> C >> N >> M >> S >> D, N) {
        S--; D--;
        graph g(N);
        for(int i=0; i<M; ++i) {
            int a, b, f;
            cin >> a >> b >> f;
            a--; b--;
            g[a].push_back((edge){b, f});
            g[b].push_back((edge){a, f});
        }

        int res = INF;
        using state = tuple<int, int, int>;
        vector<vector<int>> d(N, vector<int>(C+1, INF));
        d[S][C] = 0;
        priority_queue<state, vector<state>, greater<state>> que;
        que.push(make_tuple(0, S, C));
        while(!que.empty()) {
            int cur, v, c;
            tie(cur, v, c) = que.top();
            que.pop();
            if(d[v][c] < cur) {
                continue;
            }
            if(v == D) {
                res = min(res, d[v][c]);
            }
            for(auto& e : g[v]) {
                if(c > 0 && d[e.to][c-1] > d[v][c] + e.cost / 2) {
                    d[e.to][c-1] = d[v][c] + e.cost / 2;
                    que.push(make_tuple(d[e.to][c-1], e.to, c-1));
                }
                if(d[e.to][c] > d[v][c] + e.cost) {
                    d[e.to][c] = d[v][c] + e.cost;
                    que.push(make_tuple(d[e.to][c], e.to, c));
                }
            }
        }
        cout << res << endl;
    }
}
