#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

struct edge {
    int to, cost;
};

struct state {
    int v, d, rest;
    bool operator<(const state& s)const{
        return d>s.d;
    }
};

int dijk(int s, int g, const vector<vector<edge>>& G, int c){

    vector<int> d(G.size(), 1000000000);
    d[s] = 0;

    priority_queue<state> q;
    q.push({ s, 0, c });

    vector<vector<bool>> vis(G.size(), vector<bool>(c + 1, false));

    while (q.size()){
        state sta = q.top();
        q.pop();

        int v = sta.v;

        int rest = sta.rest;

        if (vis[v][rest]) continue;
        vis[v][rest] = true;

        rep(i, G[v].size()){

            int to = G[v][i].to;
            int cost = G[v][i].cost;


            if (d[to] > sta.d + cost){

                d[to] = sta.d + cost;
                q.push({ to, sta.d + cost, rest });
            }

            if (d[to] > sta.d + cost / 2 && rest != 0){

                d[to] = sta.d + cost / 2;
                q.push({ to, sta.d + cost / 2, rest - 1 });
            }
        }
    }
    return d[g];
}

int main(){
    while (1){
        int c, V, E, s, d;
        cin >> c >> V >> E >> s >> d;
        if (c == 0) break;
        vector<vector<edge>> G(V);
        s--; d--;
        rep(i, E){
            int a, b, c;
            cin >> a >> b >> c;
            a--; b--;
            G[a].push_back({ b, c });
            G[b].push_back({ a, c });
        }
        cout << dijk(s, d, G, c) << endl;
    }
}