#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
#define INF 1000000

int main() {
    while (true) {
        int c, n, m, s, d;
        cin >> c >> n >> m >> s >> d;
        
        if (c==0 && n==0 && m==0 && s==0 && d==0) {
            break;
        }
        
        s -= 1;
        d -= 1;
        
        vector<P> adj_list[n*(c+1)];
    
        for (int i=0; i<m; i++) {
            int ai, bi, fi;
            cin >> ai >> bi >> fi;
            ai -= 1;
            bi -= 1;
        
            for (int j=0; j<=c; j++) {
                adj_list[ai*(c+1)+j].push_back(P(bi*(c+1)+j, fi));
                adj_list[bi*(c+1)+j].push_back(P(ai*(c+1)+j, fi));
            
                if (j>0) {
                    adj_list[ai*(c+1)+j].push_back(P(bi*(c+1)+j-1, fi/2));
                    adj_list[bi*(c+1)+j].push_back(P(ai*(c+1)+j-1, fi/2));
                }
            }
        }
        
        priority_queue<P, vector<P>, greater<P>> pq;
        int dist[n*(c+1)];
        
        for (int i=0; i<n*(c+1); i++) {
            dist[i] = INF;
        }
        
        dist[s*(c+1)+c] = 0;
        pq.push(P(0, s*(c+1)+c));
        
        while (pq.size()) {
            P p = pq.top();
            pq.pop();
            
            int d = p.first;
            int v = p.second;
            
            if (dist[v]<d) {
                continue;
            }
            
            for (int i=0; i<adj_list[v].size(); i++) {
                int nv = adj_list[v][i].first;
                int w = adj_list[v][i].second;
                
                if (dist[nv]>dist[v]+w) {
                    dist[nv] = dist[v]+w;
                    pq.push(P(dist[nv], nv));
                }
            }
        }
        
        int ans = INF;
        
        for (int i=0; i<=c; i++) {
            ans = min(ans, dist[d*(c+1)+i]);
        }
        
        cout << ans << endl;
    }
}
