#include <iostream>
#include <list>
#include <queue>
using namespace std;

#define INF 100000000

struct Edge {
    int dst, fare;
    Edge(int d, int f) {
        dst = d;
        fare = f;
    }
};

struct Town {
    list<Edge*> edge;
};

struct Vertex {
    int c, tid, cost;
    Vertex (int ticket_count, int town_id, int icost) {
        c = ticket_count;
        tid = town_id;
        cost = icost;
    }
    void dump() {
        cout << "[" << c << "]" << " " << tid << "(" << cost << ")" << endl;
    }
};

bool operator<(const Vertex &a, const Vertex &b) {
    return a.cost > b.cost;
}

int main() {
    int c, n, m, s, d, a, b, f, i, j;
    while (cin >> c >> n >> m >> s >> d, c) {
        Town town[n+1];
        int cost[c+1][n+1];
        for (i = 0; i < m; i++) {
            cin >> a >> b >> f;
            town[a].edge.push_back(new Edge(b, f));
            town[b].edge.push_back(new Edge(a, f));
        }
        for (i = 0; i <= c; i++) {
            for (j = 1; j <= n; j++) {
                cost[i][j] = INF;
            }
        }
        priority_queue<Vertex*> q;
        cost[0][s] = 0;
        Vertex *v = new Vertex(0, s, 0);
        q.push(v);
        while (!q.empty()) {
            v = q.top(); q.pop();
            if (v->tid == d) {
                if (v->c == c) {
                    delete v;
                    break;
                }
                delete v;
                continue;
            }
            list<Edge*> e = town[v->tid].edge;
            for (list<Edge*>::iterator itr = e.begin();
                 itr != e.end(); itr++) {
                int ncost = v->cost + (*itr)->fare;
                int dst = (*itr)->dst;
                if (ncost < cost[v->c][dst]) {
                    cost[v->c][dst] = ncost;
                    q.push(new Vertex(v->c, dst, ncost));
                }
                if (v->c < c) {
                    ncost = v->cost + (*itr)->fare / 2;
                    if (ncost < cost[v->c+1][dst]) {
                        cost[v->c+1][dst] = ncost;
                        q.push(new Vertex(v->c+1, dst, ncost));
                    }
                }
            }
            delete v;
        }
        int min_cost = INF;
        for (i = 0; i <= c; i++) {
            if (cost[i][d] < min_cost) min_cost = cost[i][d];
        }
        cout << min_cost << endl;
    }
    return 0;
}