#include <bits/stdc++.h>

using namespace std;

struct Node {
    Node(int s, int t, int c) : s(s), t(t), c(c) {}

    int s, t, c;

    bool operator<(const Node &rhs) const {
        return c > rhs.c;
    }
};

int main() {
    int c, n, m, s, d;
    while (cin >> c >> n >> m >> s >> d && n) {
        --s, --d;
        vector<vector<Node> > g(n);

        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            --a, --b;
            g[a].push_back(Node(b, 0, c));
            g[b].push_back(Node(a, 0, c));
            g[a].push_back(Node(b, 1, c / 2));
            g[b].push_back(Node(a, 1, c / 2));
        }
        priority_queue<Node> Q;
        Q.push(Node(s, c, 0));
        bool flg[111][11] = {};
        while (Q.size()) {
            Node q = Q.top();
            Q.pop();
            if (flg[q.s][q.t]) continue;
            if (q.s == d) {
                cout << q.c << endl;
                break;
            }
            flg[q.s][q.t] = true;
            for (auto e : g[q.s]) {
                if (q.t >= e.t) {
                    Q.push(Node(e.s, q.t - e.t, q.c + e.c));
                }
            }
        }
    }
}
