#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

#define MAX_N 101
#define INF 1 << 28

struct edge_t {
    int from, to, cost;
    edge_t(int from=0, int to=0, int cost=0) :
        from(from), to(to), cost(cost) {}
};

struct state_t {
    int city;   // 現在地
    int coupon; // 残り割引券枚数
    int cost;   // 現在地までにかかった金額
    state_t(int city=0, int coupon=0, int cost=0) :
        city(city), coupon(coupon), cost(cost) {}
    bool operator>(const state_t &o) const {
        return cost == o.cost ? coupon < o.coupon : cost > o.cost;
    }
    bool operator<(const state_t &o) const {
        return cost == o.cost ? coupon > o.coupon : cost < o.cost;
    }
};

int c, n, m, s, d;
vector<edge_t> graph[MAX_N];

int dijkstra() {
    int cost[n+1][c+1];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= c; j++)
            cost[i][j] = INF;

    priority_queue<state_t, vector<state_t>, greater<state_t> > q;

    cost[s][c] = 0;

    q.push(state_t(s, c, 0));

    while (!q.empty()) {
        state_t p = q.top(); q.pop();

        for (int i = 0; i < graph[p.city].size(); i++) {
            edge_t e = graph[p.city][i];

            // クーポン券を使わないとき
            if (cost[e.to][p.coupon] > cost[e.from][p.coupon] + e.cost) {
                cost[e.to][p.coupon] = cost[e.from][p.coupon] + e.cost;
                q.push(state_t(e.to, p.coupon, cost[e.to][p.coupon]));
            }

            // クーポン券を使うとき
            if (p.coupon > 0) {
                if (cost[e.to][p.coupon-1] > cost[e.from][p.coupon] + e.cost / 2) {
                    cost[e.to][p.coupon-1] = cost[e.from][p.coupon] + e.cost / 2;
                    q.push(state_t(e.to, p.coupon-1, cost[e.to][p.coupon-1]));
                }
            }
        }
    }

    int min_cost = INF;
    for (int i = 0; i <= c; i++) 
        min_cost = min(min_cost, cost[d][i]);
    return min_cost;
}

int main() {
    while (cin >> c >> n >> m >> s >> d) {
        if (c == 0 && n == 0 && m == 0 && s == 0 && d == 0) break;
        for (int i = 0; i <= n; i++) graph[i].clear();
        for (int i = 0; i < m; i++) {
            int a, b, f; cin >> a >> b >> f;
            graph[a].push_back(edge_t(a, b, f));
            graph[b].push_back(edge_t(b, a, f));
        }
        cout << dijkstra() << endl;
    }
    return 0;
}
    