#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <functional>

using namespace std;

typedef pair<int, int> P;
const int N = 100, INF = 10e6;
int edge[N][N];

vector<int> dijkstra(int n, int s, int d){
    priority_queue<P> pq;
    vector<int> ret;
    int visited[n], now = d;
    fill(visited, visited + n, 0);
    pq.push(make_pair(1, s));
    visited[s] = 1;
    while(!pq.empty()){
        P t = pq.top();
        pq.pop();
        visited[t.second] = t.first;
        if(t.second == d) break;
        for(int i = 0;i < n;++i){
            if(edge[t.second][i] != INF && !visited[i]){
                pq.push(make_pair(t.first + 1, i));
            }
        }
    }
    while(now != s){
        int m = INF, t = now;
        for(int i = 0;i < n;++i){
            if(visited[i] == visited[now] - 1 && edge[now][i] != INF){
                m = min(m, edge[now][i]);
                t = m == edge[now][i] ? i : t;
            }
        }
        ret.push_back(m);
        now = t;
    }
    return ret;
}

int main(){
    int c, n, m, s, d;
    while(cin >> c >> n >> m >> s >> d, c){
        int a, b, f, res = 0;
        --s; --d;
        for(int i = 0;i < N;++i){
            fill(edge[i], edge[i] + N, INF);
        }
        for(int i = 0;i < m;++i){
            cin >> a >> b >> f;
            --a; --b;
            edge[a][b] = edge[b][a] = f;
        }
        vector<int> r = dijkstra(n, s, d);
        sort(r.begin(), r.end(), greater<int>());
        vector<int>::iterator vit = r.begin();
        for(;vit != r.end();++vit){
            if(c != 0){
                *vit = *vit / 2;
                --c;
            }
            res += *vit;
        }
        cout << res << endl;
    }
    return 0;
}