#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct line {
    ll a, b, f;
};
using pllll = pair<ll, ll>;
using pl6 = pair<ll, pair<ll, ll>>;
struct edge {
    ll dstb, dstc, cost;
};
int main() {
    
    ll c, n, m, s, d;
    while (cin >> c >> n >> m >> s >> d, c) {

        s--; d--;

        vector<line> l(m, line{0, 0, 0});
        for (ll i = 0; i < m; i++) {
            cin >> l[i].a >> l[i].b >> l[i].f;
            l[i].a--; l[i].b--;
            if (l[i].a > l[i].b) swap(l[i].a, l[i].b);
        }

        sort(l.begin(), l.end(), [](line &i, line &j) -> bool {
                 if (i.a != j.a) return i.a < j.a;
            else if (i.b != j.b) return i.b < j.b;
            else return i.f < j.f;
        });

        // 被った路線はなかったことに
        for (ll i = m; --i; ) {
            if (l[i].a == l[i-1].a && l[i].b == l[i-1].b) {
                l.erase(l.begin() + i);
            }
        }
        m = l.size();

        
        // 無向グラフを構築
        vector<vector<vector<edge>>> g(n, vector<vector<edge>>(c+1));
        for (ll i = m; i--; ) {
            ll a = l[i].a;
            ll b = l[i].b;
            ll f = l[i].f;
            for (ll c0 = c; c0 >= 0; c0--) {
                g[a][c0].push_back(edge{b, c0, f});
                g[b][c0].push_back(edge{a, c0, f});
                if (c0 > 0) {
                    g[a][c0].push_back(edge{b, c0-1, f/2});
                    g[b][c0].push_back(edge{a, c0-1, f/2});
                }
            }
        }

        // 拡張Dijkstra
        vector<vector<ll>> dp(n, vector<ll>(c+1, 0x7FFFFFFFLL));
        vector<vector<bool>> determined(n, vector<bool>(c+1, false));
        priority_queue<pl6, vector<pl6>, greater<pl6>> q;
        q.push(pl6(0, pllll(s, c)));
        dp[s][c] = 0;
        while (!q.empty()) {
            pl6 cv = q.top(); q.pop();
            pllll v = cv.second;
            ll vf = dp[v.first][v.second];
            if (determined[v.first][v.second]) continue;
            determined[v.first][v.second] = true;
            for (edge &ed : g[v.first][v.second]) {
                if (determined[ed.dstb][ed.dstc]) continue;
                if (vf + ed.cost < dp[ed.dstb][ed.dstc]) {
                    q.push(pl6(vf + ed.cost, pllll(ed.dstb, ed.dstc)));
                    dp[ed.dstb][ed.dstc] = vf + ed.cost;
                }
            }
        }

        ll ans = 0x7FFFFFFFLL;
        for (ll i = 0; i <= c; i++) {
            ans = min(ans, dp[d][i]);
        }
        cout << ans << endl;

    }

}
