#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class Edge
{
public:
    int to, cost;
    Edge(){};
    Edge(int to0, int cost0){to = to0; cost = cost0;}
};

void shortestPath(const vector<vector<Edge> >& edges, int start, vector<int>& dist)
{
    dist.assign(edges.size(), INT_MAX);
    dist[start] = 0;
    priority_queue<pair<int,int> ,vector<pair<int,int> >, greater<pair<int,int> > > q;
    q.push(make_pair(0, start));

    while(!q.empty()){
        pair<int, int> p = q.top();
        q.pop();
        int v = p.second;
        if(dist[v] < p.first)
            continue;
        for(unsigned i=0; i<edges[v].size(); ++i){
            Edge e = edges[v][i];
            if(dist[v] + e.cost < dist[e.to]){
                dist[e.to] = dist[v] + e.cost;
                q.push(make_pair(dist[e.to], e.to));
            }
        }
    }
}

int main()
{
    for(;;){
        int c, n, m, s, d;
        cin >> c >> n >> m >> s >> d;
        if(c == 0)
            return 0;
        -- s;
        -- d;

        vector<vector<Edge> > edges((c+1) * n);
        for(int i=0; i<m; ++i){
            int a, b, f;
            cin >> a >> b >> f;
            -- a;
            -- b;

            for(int j=0; j<=c; ++j){
                edges[a+j*n].push_back(Edge(b+j*n, f));
                edges[b+j*n].push_back(Edge(a+j*n, f));
            }
            for(int j=0; j<c; ++j){
                edges[a+j*n].push_back(Edge(b+(j+1)*n, f/2));
                edges[b+j*n].push_back(Edge(a+(j+1)*n, f/2));
            }
        }

        vector<int> dist;
        shortestPath(edges, s, dist);
        int ret = INT_MAX;
        for(int i=0; i<=c; ++i)
            ret = min(ret, dist[d+i*n]);
        cout << ret << endl;
    }
}