#include<algorithm>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  unsigned i,j;
  unsigned a[100][100],b[100][11],c[100][11],m,n,o,u,v;
  pair<pair<unsigned,unsigned>,unsigned> mn;
  while(cin>>m>>n>>o>>u>>v&&m+n+o+u+v){
    u--;
    v--;
    memset(a,-1,sizeof(a));
    for(i=0;i<o;i++){
      int p,q,r;
      cin>>p>>q>>r;
      p--;
      q--;
      a[p][q]=a[q][p]=r;
    }
    memset(b,0,sizeof(b));
    memset(c,-1,sizeof(c));
    c[u][0]=0;
    mn.first.first=u;
    mn.first.second=0;
    mn.second=0;
    while(mn.first.first!=v){
      b[mn.first.first][mn.first.second]=1;
      for(i=0;i<n;i++){
	if((int)a[mn.first.first][i]!=-1){
	  c[i][mn.first.second]=min(c[i][mn.first.second],mn.second+a[mn.first.first][i]);
	  if(mn.first.second<m)
	    c[i][mn.first.second+1]=min(c[i][mn.first.second+1],mn.second+a[mn.first.first][i]/2);
	}
      }
      mn.second=-1;
      for(i=0;i<m+1;i++){
	for(j=0;j<n;j++){
	  if(b[j][i]==0&&mn.second>c[j][i]){
	    mn.first.first=j;
	    mn.first.second=i;
	    mn.second=c[j][i];
	  }
	}
      }
    }
    cout<<mn.second<<endl;
  }
  return 0;
}    