#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef pair<int,int> pii;
typedef pair<int,pii> pip;

class Dijkstra{
private:
    struct edge {int to,cost;};
    vector<vector<edge> > g;
    int n;

public:
    Dijkstra(int size){
        g.resize(size);
        n = size;
    }
    vector<vector<int> > dist;
    void add(int a, int b, int c){
        edge e1 = {b,c}, e2 = {a,c};
        g[a].push_back(e1);
        g[b].push_back(e2);
    }
    int calc(int s,int t,int ma){
        priority_queue<pip,vector<pip>,greater<pip> > q;
        int n = g.size();
        dist = vector<vector<int> > (n, vector<int>(ma+1,1e9));
        dist[s][0] = 0;
        q.push(pip(0,pii(s,0)));
        while(!q.empty()){
            pip p = q.top();
            q.pop();
            int c = p.first;
            pii node = p.second;
            if(dist[node.first][node.second] < c)continue;
            rep(i,g[node.first].size()){
                edge e = g[node.first][i];
                if(dist[e.to][node.second] > dist[node.first][node.second] + e.cost){
                    dist[e.to][node.second] = dist[node.first][node.second] + e.cost;
                    q.push(pip(dist[e.to][node.second],pii(e.to,node.second)));
                }
                if(node.second < ma){
                    if(dist[e.to][node.second+1] > dist[node.first][node.second] + e.cost/2){
                        dist[e.to][node.second+1] = dist[node.first][node.second] + e.cost/2;
                        q.push(pip(dist[e.to][node.second+1],pii(e.to,node.second+1)));
                    }
                }
            }
        }
        int ret = 1e9;
        rep(i,ma+1)ret = min(ret, dist[t][i]);
        return ret;
    }
};

int main(){
    int c,n,m,s,d;
    while(cin >> c >> n >> m >> s >> d, n){
        Dijkstra dij(n);
        rep(i,m){
            int a,b,f;
            cin >> a >> b >> f;
            dij.add(a-1,b-1,f);
        }
        cout << dij.calc(s-1,d-1,c) << endl;
    }
}

