#include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

#define to first
#define dist second

const int INF = 1e9;

int main() {
    int c, n, m, s, d;
    while (cin >> c >> n >> m >> s >> d, c) {
        s--, d--;
        vector <vector <pair <int, int>>> G(n);
        rep (i, m) {
            int a, b, f;
            cin >> a >> b >> f;
            a--, b--;
            G[a].emplace_back(b, f);
            G[b].emplace_back(a, f);
        }

        // state -> (dist, now, num of ticket)
        using state = tuple <int, int, int>;
        priority_queue <state> que;
        vector <vector <int>> dp(n, vector <int> (c + 1, INF));
        dp[s][0] = 0;
        que.emplace(0, s, 0);

        while (!que.empty()) {
            state p = que.top(); que.pop();
            int dist, now, numOfTicket;
            tie(dist, now, numOfTicket) = p;

            for (auto & next : G[now]) {
                if (numOfTicket < c && dp[next.to][numOfTicket + 1] > dist + next.dist / 2) {
                    dp[next.to][numOfTicket + 1] = dist + next.dist / 2;
                    que.emplace(dp[next.to][numOfTicket + 1], next.to, numOfTicket + 1);
                }
                if (dp[next.to][numOfTicket] > dist + next.dist) {
                    dp[next.to][numOfTicket] = dist + next.dist;
                    que.emplace(dp[next.to][numOfTicket], next.to, numOfTicket);
                }
            }
        }
        int ans = INF;
        rep (i, c + 1) ans = min(ans, dp[d][i]);
        cout << ans << endl;
    }
    return 0;
}
