#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=1e9;
struct edge{
    int to,cost;
    edge(int a,int b):to(a),cost(b){}
};
struct data{
    int At,cost,cnt;
    data(int a,int b,int c):At(a),cost(b),cnt(c){}
    bool operator>(const data &d)const{
        return (cost>d.cost);
    }
};
int main(){
    int c,n,m,s,d;
    while(cin>>c>>n>>m>>s>>d){
        if(!(c||n||m||s||d))break;
        s--;d--;
        vector<vector<edge> >V(n);
        vector<vector<int> >D(n,vector<int>(c+1,INF));
        for(int i=0;i<m;i++){
            int a,b,f;
            cin>>a>>b>>f;
            a--;b--;
            V[a].push_back(edge(b,f));
            V[b].push_back(edge(a,f));
        }

        priority_queue<data,vector<data>,greater<data> >Q;
        Q.push(data(s,0,0));

        while(!Q.empty()){
            data latte=Q.top();Q.pop();
            int At=latte.At,cost=latte.cost,cnt=latte.cnt;
            if(cnt>c)continue;
            if(D[At][cnt]<cost)continue;
            D[At][cnt]=cost;
            for(int i=0;i<V[At].size();i++){
                edge e=V[At][i];
                Q.push(data(e.to,cost+e.cost,cnt));
                Q.push(data(e.to,cost+e.cost/2,cnt+1));
            }
        }
        cout<<*min_element(D[d].begin(),D[d].end())<<endl;
    }
    return 0;
}