#include<iostream>
using namespace std;
const int INF = (1<<21);
int G[101][101];
int c,n,m,s,d;

int dij(){
  int D[101][11];
  bool V[101][11];
  for(int i=0;i<n;i++){
    for(int j=0;j<c+1;j++){
      D[i][j]=INF;
      V[i][j]=false;
    }
  }
  D[s][c]=0;
  while(1){
    int minv=INF,u,w;
    for(int i=0;i<n;i++){
      for(int j=0;j<c+1;j++){
	if(!V[i][j] && minv>D[i][j]){
	  minv=D[i][j];
	  u=i;
	  w=j;
	}
      }
    }
    
    V[u][w]=true;
    if(minv == INF) break;
    for(int i=0;i<n;i++){
      if(G[u][i] == INF) continue;
      D[i][w]=min(D[i][w],D[u][w]+G[u][i]);
      if( w ){
	D[i][w-1]=min(D[i][w-1],D[u][w]+G[u][i]/2);
      }
    }
  }

  int minv=INF;
  for(int i=0;i<c+1;i++){
    if(D[d][i]<minv){
      minv=D[d][i];
    }
  }

  return minv;  
}

int main(){
  
  while(cin>> c>> n>> m>> s>> d && c){
    d--;
    s--;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	G[i][j]=INF;
      }
    }
    
    for(int i=0;i<m;i++){
      int a,b,f;
      cin>> a>> b>> f;
      a--;
      b--;
      G[a][b]=G[b][a]=f;
    }
    
    cout<< dij()<< endl;
  }
}