#include <iostream>
#include <vector>
#include <queue>
#include <map>
#define INF (1 << 26)
#define fr first
#define sc second
using namespace std;

typedef pair<int,int> S;
typedef pair<S,int> P;
struct edge{
    int to,cost; edge(){}
    edge(int to,int cost):to(to),cost(cost){}
};

int c,n,m,s,d,costed[1024][101];
vector< vector<edge> > info(1024);

void init(){
    for(int i=0;i<1024;i++){
        for(int j=0;j<101;j++) costed[i][j] = INF;
    }
    info.resize(0); info.resize(1024);
}

void add_info(){
    int a,b,f;
    cin >> a >> b >> f;
    info[a].push_back(edge(b,f));
    info[b].push_back(edge(a,f));
}

int Dijkstra(){
    priority_queue<P,vector<P>,greater<P> > que;
    que.push(P(S(0,s),c));  costed[s][c] = 0;
    while(!que.empty()){
        P p = que.top(); que.pop();
        int now = p.fr.sc,c = p.fr.fr,tic = p.sc;
        if(now == d) return c;
        for(int i=0;i<info[now].size();i++){
            edge e = info[now][i];
            if(e.cost + c < costed[e.to][tic]){
                que.push(P(S(e.cost+c,e.to),tic));
                costed[e.to][tic] = e.cost + c;
            }
            if(tic != 0){
                if(e.cost/2 + c < costed[e.to][tic-1]){
                    que.push(P(S(c+e.cost/2,e.to),tic-1));
                    costed[e.to][tic-1] = e.cost/2 + c;
                }
            }
        }
    }
}

int main(){
    while(cin>>c>>n>>m>>s>>d,c||n||m||s||d){
        init();
        for(int i=0;i<m;i++) add_info();
        cout << Dijkstra() << endl;
    }
}