#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;
    }
}