//04
#include<iostream>
#include<algorithm>

using namespace std;

struct edge{
  int a,b,f;
  edge(int aa,int bb,int ff){
    a=aa;
    b=bb;
    f=ff;
  }
  edge(){};
};

int main(){
  for(int c,n,m,s,ds;cin>>c>>n>>m>>s>>ds,c|n|s|m|ds;){
    edge e[500];
    for(int i=0;i<m;i++){
      int a,b,f;
      cin>>a>>b>>f;
      e[i]=edge(a,b,f);
    }
    int d[101][11];
    fill_n(d[0],101*11,1<<29);
    d[s][c]=0;
    for(int l=0;l<n;l++){
      for(int i=0;i<m;i++){
	for(int j=0;j<2;j++){
	  int s=e[i].a,t=e[i].b;
	  if(j){
	    swap(s,t);
	  }
	  for(int k=0;k<=10;k++){
	    d[t][k]=min(d[t][k],d[s][k]+e[i].f);
	    if(k){
	      d[t][k-1]=min(d[t][k-1],d[s][k]+e[i].f/2);
	    }
	  }
	}
      }
    }
    cout<<*min_element(d[ds],d[ds+1])<<endl;
  }
  return 0;
}