#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

template <typename T>
struct Edge { int src, dst; T cost;
    Edge(int dst, T cost) : src(-1), dst(dst), cost(cost) { }
    Edge(int src, int dst, T cost) : src(src), dst(dst), cost(cost) { }
};
template <typename T> using Edges = vector<Edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
template <typename T> using Matrix = vector<vector<T>>;

template <typename T>
vector<vector<T>> dijkstra(const WeightedGraph<T> &g, int s, int c) {
    const T INF = numeric_limits<T>::max();
    vector<vector<T>> dp(g.size(), vector<T>(c + 1, INF));
    using Pi = tuple<T, int, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    dp[s][c] = 0; que.emplace(dp[s][c], s, c);
    while (!que.empty()) {
        T cost; int v, cc; tie(cost, v, cc) = que.top(); que.pop();
        if (dp[v][cc] < cost) continue;
        for (auto &e: g[v]) {
            int nv = e.dst; T nc = e.cost;
            if (cc) {
                if (dp[nv][cc - 1] > dp[v][cc] + nc / 2) {
                    dp[nv][cc - 1] = dp[v][cc] + nc / 2;
                    que.emplace(dp[nv][cc - 1], nv, cc - 1);
                }
            }
            if (dp[nv][cc] <= dp[v][cc] + nc) continue;
            dp[nv][cc] = dp[v][cc] + nc;
            que.emplace(dp[nv][cc], nv, cc);
        }
    }
    return dp;
}

int main() {
    int c, n, m, s, d;
    while (cin >> c >> n >> m >> s >> d, s--, d--, n) {
        WeightedGraph<int> g(n);
        while (m--) {
            int a, b, f; cin >> a >> b >> f; a--, b--;
            /*if (a != d) */g[a].emplace_back(b, f);
            /*if (b != d) */g[b].emplace_back(a, f);
        }
        auto res = dijkstra(g, s, c)[d];
        cout << *min_element(res.begin(), res.end()) << endl;
    }
    return 0;
}
