// Original C++ solution (slower):
#include "bits/stdc++.h"



using namespace std;



typedef vector<int> vi;

typedef pair<int,int> pii;

typedef long long ll;



#define rep(i,n) for(ll i=0;i<(ll)(n);i++)

#define all(a)  (a).begin(),(a).end()

#define pb push_back

#define INF 999999999



int c,n,m;

int pass[200][200];



double d[200][20];

bool used[200][20];



int dijk(int s,int g){

    rep(i,200)rep(j,20){

        d[i][j]=INF;

        used[i][j]=false;

    }

    

    d[s][c]=0;

    

    while(1){

        int v=-1;

        int w=-1;

        rep(u,n){

            rep(i,c+1){

                if( !used[u][i] && (v==-1||d[u][i]<d[v][w]) )v=u,w=i;

            }

        }

        if(v==-1)break;

        

        used[v][w]=true;

        

        rep(u,n){

            d[u][w] = min(d[u][w] , d[v][w] + pass[v][u] );

//            cout<<"d["<<u<<"]["<<w<<"]="<<d[u][w]<<endl;

            if(w-1>=0 && pass[v][u]!=INF){

                d[u][w-1] = min(d[u][w-1] , d[v][w] + (pass[v][u]/2.0) );

//                cout<<"d["<<u<<"]["<<w-1<<"]="<<d[u][w-1]<<endl;

            }

        }

    }

    double ret=INF;

    rep(i,c+1){

        ret = min(ret,d[g][i]);

    }

    return ret;

}





int main(){

    int s,g;

    while(cin>>c>>n>>m>>s>>g){

        if(c==0&&n==0&&m==0&&s==0&&g==0)break;

        

        s--,g--;

        rep(i,200)rep(j,200)pass[i][j]=INF;

        rep(i,200)pass[i][i]=0;

        

        rep(i,m){

            int a,b,f;

            cin>>a>>b>>f;

            a--,b--;

            pass[a][b]=pass[b][a]=f;

        }

        

    cout<<dijk(s,g)<<endl;

    }

}

// Optimized solution to the same problem (faster):
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<int,pii> piii;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)

#define all(a)  (a).begin(),(a).end()

#define pb push_back

#define INF 999999999

#define MAX_V 100



struct edge{int to,cost;};

vector<edge> G[MAX_V];

int d[MAX_V][10];

int c,n,m,s,g;



int dijkstra(int s,int V){

    priority_queue< piii,vector<piii>,greater<piii> > que;

    rep(i,MAX_V)rep(j,10)d[i][j]=INF;

    d[s][c]=0;

    que.push(make_pair(0,pii(s,c)));

    

    while(que.size()){

        piii p=que.top();

        que.pop();

        

        int v=p.second.first ;

        int w=p.second.second;

        if(d[v][w]<p.first)continue;

        

        rep(i,G[v].size()){

            edge e=G[v][i];

            rep(j,10){

                if(d[e.to][j]>d[v][j]+e.cost){

                    d[e.to][j]=d[v][j]+e.cost;

                    que.push(make_pair(d[e.to][j],pii(e.to,j)));

                }

            }

            for(int j = 1;j<10;j++){

                if(d[e.to][j-1]>d[v][j]+e.cost/2){

                    d[e.to][j-1]=d[v][j]+e.cost/2;

                    que.push(make_pair(d[e.to][j-1],pii(e.to,j-1)));

                }

            }

        }

    }

    int mini = INF;

    rep(i,10){

        mini = min(mini,d[V][i]);

    }

    return mini;

}



int main(){

    while(cin>>c>>n>>m>>s>>g&&c&&n&&m&&s&&g){

        rep(i,MAX_V)rep(j,10)G[i].clear();

        s--,g--;

        rep(i,m){

            int a,b,f;

            cin>>a>>b>>f;

            a--,b--;

            G[a].pb(edge{b,f});

            G[b].pb(edge{a,f});

        }

        cout<<dijkstra(s,g)<<endl;

    }

}

// Fastest known solution for this problem: