#include <cstdio>
#include <algorithm>
#include <complex>
#include <queue>
#include <map>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)

typedef long long ll;
struct edge {int to, cost;};
typedef pair<int, int> P;
typedef complex<double> C;

const int INF = 99999999;
const int MAX_V = 110;
const int MAX_E = 510;

int cost[MAX_V][MAX_V];
int d[MAX_V], d2[MAX_V];
bool used[MAX_V];
int pre[MAX_V], pre2[MAX_V];
int V, E;
int c, s, g;

void init_cost() {
    REP(i, V) REP(j, V) cost[i][j] = INF;
}

//s: start
void dijkstra(int s, int *d, int *pre) {
    REP(i, V) d[i] = INF;
    REP(i, V) used[i] = false;
    REP(i, V) pre[i] = -1;
    d[s] = 0;

    while (true) {
        int v = -1;
        REP(u, V) if (!used[u] && (v == -1 | d[u] < d[v])) v = u;

        if (v == -1) break;
        used[v] = true;

        REP(u, V) {
            if (d[u] > d[v] + cost[v][u]) {
                d[u] = d[v] + cost[v][u];
                pre[u] = v;
            }
        }
    }
}

//t: terminal
vector<int> get_path(int t, int *pre) {
    vector<int> path;
    for (; t != -1; t = pre[t]) path.pb(t);
    reverse(ALL(path));
    return path;
}

void solve() {
    dijkstra(s, d, pre);
    dijkstra(g, d2, pre2);

    int ans = INF;

    REP(k, V) {
        vector<int> cost_vec;

        vector<int> path = get_path(k, pre);
        REP(i, path.size() - 1) {
            cost_vec.pb(cost[path[i]][path[i+1]]);
        }

        path = get_path(k, pre2);
        REP(i, path.size() - 1) {
             cost_vec.pb(cost[path[i]][path[i+1]]);
        }

        sort(ALL(cost_vec));
        reverse(ALL(cost_vec));

        // REP(i, cost_vec.size()) printf("%d ", cost_vec[i]);
        // printf("\n");

        int sm = 0;
        REP(i, cost_vec.size()) {
            if (i < c)  sm += cost_vec[i] / 2;
            else        sm += cost_vec[i];
        }

        ans = min(ans, sm);
    }

    printf("%d\n", ans);

}

int main() {
    while (true) {
        scanf("%d%d%d%d%d", &c, &V, &E, &s, &g);
        if (!c) return 0;
        s--; g--;
        init_cost();
        REP(i, E) {
            int f, t, c;
            scanf("%d%d%d", &f, &t, &c);
            f--; t--;
            cost[f][t] = c;
            cost[t][f] = c;
        }
        solve();
    }
}