#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Edge { int from, to, cost; };
vector<Edge> edges;

int mincost[11][101];

int main() {
    int c, n, m, s, d;
    while (cin >> c >> n >> m >> s >> d, c) {
        edges.clear();
        int a, b, f;
        for (int i=0; i<m; ++i) {
            cin >> a >> b >> f;
            edges.push_back((Edge){ a, b, f });
            edges.push_back((Edge){ b, a, f });
        }
        for (int i=0; i<11; ++i) {
            for (int j=0; j<101; ++j) {
                mincost[i][j] = 10000000;
            }
        }
        mincost[0][s] = 0;
        for (int k=0; k<n; ++k) {
            for (int i=0; i<(int)edges.size(); ++i) {
                Edge &e = edges[i];
                for (int j=0; j<=c; ++j) {
                    mincost[j][e.to] = min(mincost[j][e.to], mincost[j][e.from] + e.cost);
                    if (j < c) {
                        mincost[j+1][e.to] = min(mincost[j+1][e.to], mincost[j][e.from] + e.cost / 2);
                    }
                }
            }
        }
        int res = 10000000;
        for (int i=0; i<10; ++i) {
            res = min(res, mincost[i][d]);
        }
        cout << res << endl;
    }
    return 0;
}