#include<queue>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  unsigned i;
  unsigned a[100][100],b[100][11],c[100][11],m,n,o,u,v,x,y,z;
  priority_queue<pair<unsigned,pair<unsigned,unsigned> >,vector<pair<unsigned,pair<unsigned,unsigned> > >,greater<pair<unsigned,pair<unsigned,unsigned> > > > d;
  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;
    while(d.empty()==0)
      d.pop();
    d.push(make_pair(0,make_pair(u,0)));
    for(;;){
      z=d.top().first;
      x=d.top().second.first;
      y=d.top().second.second;
      d.pop();
      if(x==v)
	break;
      if(b[x][y]==0){
	b[x][y]=1;
	for(i=0;i<n;i++){
	  if((int)a[x][i]!=-1){
	    d.push(make_pair(z+a[x][i],make_pair(i,y)));
	    if(y<m)
	      d.push(make_pair(z+a[x][i]/2,make_pair(i,y+1)));
	  }
	}
      }
    }
    cout<<z<<endl;
  }
  return 0;
}