#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <cmath>
using namespace std;

typedef pair<int, int> S;
typedef pair<int, S> P;

const int INF = 1 << 21;
const int MAX_C = 10, MAX_N = 100, MAX_M = 500;

int dp[MAX_N + 1][MAX_C + 1], w[MAX_N + 1][MAX_N + 1];
int c, n, m, s, d;

int solve()
{
    for(int i = 0; i <= MAX_N; i++) 
        for(int j = 0; j <= MAX_C; j++) 
            dp[i][j] = INF;
    
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0, S(s, c)));
    while(!que.empty()) {
        P p = que.top(); que.pop();
        int cost = p.first,  from = p.second.first, t = p.second.second;
        
        if(from == d)
            return cost;

        for(int to = 1; to <= n; to++) {
            if(cost + w[from][to] < dp[to][t]) {
                dp[to][t] = cost + w[from][to];
                que.push(P(dp[to][t], S(to, t)));
            }
        }

        if(t > 0) {
            for(int to = 1; to <= n; to++) {
                if(w[from][to] / 2 + cost < dp[to][t - 1]) {
                    dp[to][t - 1] = w[from][to] / 2 + cost;
                    que.push(P(dp[to][t-1], S(to, t - 1)));
                }
            }
        }
    }
}

int main()
{
    while(cin >> c >> n >> m >> s >> d && c || n || m) {

        for(int i = 0; i <= n; i++) 
            for(int j = 0; j <= n; j++)
                w[i][j] = INF;
        int a, b, f;
        for(int k = 0; k < m; k++) {
            cin >> a >> b >> f;
            w[a][b] = w[b][a] = f;
        }

        cout << solve() << endl;
    }
}