#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define INF 100000000
#define MAXN 110
#define MAXM 512
#define MAXC 11
typedef long long ll;

struct edge {
    int from, to, cost;
};

edge es[2*MAXM];

int c, n, m, s, d;
int dist[MAXN][MAXN];
int xdist[MAXC][MAXN];

int main(void) {
    while (1) {
        cin >> c >> n >> m >> s >> d;
        if (c == 0 && n == 0 && m == 0 && s == 0 && d == 0) break;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = INF;
            }
            dist[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int a, b, f;
            cin >> a >> b >> f;
            dist[a][b] = dist[b][a] = f;
            es[2*i].from = a; es[2*i].to = b; es[2*i].cost = f;
            es[2*i+1].from = b; es[2*i+1].to = a; es[2*i+1].cost = f;
        }
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            xdist[0][i] = dist[i][d];
        }
        for (int i = 1; i <= c; i++) {
            for (int j = 1; j <= n; j++) {
                xdist[i][j] = xdist[i-1][j];
                for (int k = 0; k < 2*m; k++) {
                    edge e = es[k];
                    xdist[i][j] = min(xdist[i][j], dist[j][e.from] + e.cost / 2 + xdist[i-1][e.to]);
                }
            }
        }
        cout << xdist[c][s] << endl;
    }
    return 0;
}