#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 100
int INF = 1000000;
int G[MAX][MAX];
int c, n, m, s, d, a, b, f;

int dijkstra(){
    int D[MAX][11];
    bool visited[MAX][11];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= c; j++) {
            D[i][j] = INF;
            visited[i][j] = false;
        }
    }
    D[s][c] = 0;
    while (true) {
        int u = 0, w = 0, minv = INF;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                if (!visited[i][j] && minv > D[i][j]) {
                    minv = D[i][j];
                    u = i;
                    w = j;
                }
            }
        }
        if (minv == INF) {
            break;
        }
        visited[u][w] = true;
        for (int v = 0; v < n; v++) {
            if (G[u][v] == INF) {
                continue;
            }
            D[v][w] = min(D[v][w], D[u][w] + G[u][v]);
            if (w) {
                D[v][w-1] = min(D[v][w-1], D[u][w] + G[u][v] / 2);
            }
        }
    }
    int minv = INF;
    for (int i = 0; i <= c; i++) {
        minv = min(minv, D[d][i]);
    }
    return minv;
}

int main()
{
    while (true) {
        cin >> c >> n >> m >> s >> d;
        if (s == 0 && d == 0) {
            break;
        }
        s--;
        d--;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                G[i][j] = INF;
            }
        }
        for (int i = 0; i < n; i++) {
            cin >> a >> b >> f;
            a--;
            b--;
            G[a][b] = G[b][a] = f;
        }
        cout << dijkstra() << endl;
    }

    return 0;
}