#include<bits/stdc++.h>
using namespace std;
#define INF (1<<29)//INF
#define F first
#define S second
#define VS vector<string>
#define VI vector<int>
#define REPI(i,s,n) for(int i=s;i<n;i++)//sからn未満の間iを回す
#define REPJ(j,s,n) for(int j=s;j<n;j++)//sからn未満の間iを回す
#define RREPI(i,s,n) for(int i=s;i>=n;i--)//sからn以下の間iを回す
#define RREPJ(j,s,n) for(int j=s;j>=n;j--)//sからn以下の間jを回す
#define ALL(a) a.begin(),a.end()//ソートとかに使える sort(ALL(vec))のように
#define SET(a,c) memset(a,c,sizeof(a));//aをc（0or1）で初期化する
#define DEBUGONE(x) cout<<#x<<" : "<<x<<endl;//デバックで一つの変数を表示
#define DEBUGTWO(x,y) cout<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<endl;//デバックで二つの変数を表示
#define DEBUGTHREE(x,y,z) cout<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<" "<<#z<<" : "<<z<<endl;//デバックで三つの変数を表示
#define OUTONE(x) cout<<x<<endl;//一つの変数を表示
#define OUTTWO(x,y) cout<<x<<" "<<y<<endl;//二つの変数を表示
#define OUTTHREE(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl;//三つの変数を表示
typedef long long int64;
typedef pair<string,int> Psi;
typedef pair<int,int> Pii;
typedef pair<int,Pii> Ppii;
typedef struct{
  vector<Pii> to;
  int mins;
}Edge;
bool flag[105];
main(){
  int c,n,m,s,d;
  while(cin>>c>>n>>m>>s>>d,c||n||m||s||d){
    Edge edge[105];
    for(int i=1;i<=n;i++){
      edge[i].to.clear();
      flag[i]=true;
      edge[i].mins=INF;
    }
    REPI(i,0,m){
      int from,to,cost;
      cin>>from>>to>>cost;
      edge[from].to.push_back(Pii(to,cost));
      edge[to].to.push_back(Pii(from,cost));
    }
    priority_queue<Ppii,vector<Ppii>,greater<Ppii> > que;//F=cost,S.F=now,S.S=ticket
    que.push(Ppii(0,Pii(s,c)));
    while(!que.empty()){
      Ppii now=que.top();
      que.pop();
      int nowc=now.F,nowp=now.S.F,nowt=now.S.S;
      //DEBUGTHREE(nowc,nowp,nowt);
      if(nowp==d){
	OUTONE(nowc);
	break;
      }
      Edge nowe=edge[nowp];
      flag[nowp]=false;
      int size=nowe.to.size();
      REPI(i,0,size){
	int nextp=nowe.to[i].F;
	//DEBUGTWO(nowe.to[i].F,nowe.to[i].S);
	if(flag[nextp]==true&&edge[nextp].mins>nowc+edge[nowp].to[i].S){
	  //cout<<"A"<<endl;
	  edge[nextp].mins=nowc+edge[nowp].to[i].S;
	  que.push(Ppii(nowc+edge[nowp].to[i].S,Pii(nextp,nowt)));
	}
	if(nowt>0&&flag[nextp]==true&&edge[nextp].mins>nowc+(edge[nowp].to[i].S/2)){
	  //cout<<"B"<<endl;
	  edge[nextp].mins=nowc+(edge[nowp].to[i].S);
	  que.push(Ppii(nowc+(edge[nowp].to[i].S/2),Pii(nextp,nowt-1)));
	}
      }
    }
  }
}