#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
const int MAX_V =100;

int c,n,m,d;//割引券,街の数,路線の数,出発地,目的地
int a,b,f;//バスの始点、終点,料金
int cd[11][MAX_V];
int used[MAX_V];
int cost[MAX_V][MAX_V];
const int INF =10000000;
int mv;
int max1,max2;
int max1V,max2V;
void dijkstra(int s){
  for(int i = 0;i <=c;i++){
    for(int j = 0;j <n;j++){
      if(j !=s)
	cd[i][j] =INF;
      else
	cd[i][s] =0;
    }
  }
  int v;
  for(int k = 0;k <=c;k++){
    fill(used,used+MAX_V,-1);
    while(true){
      v = -1;
    for(int u = 0;u <n;u++){
      if(used[u] ==-1&&(v ==-1||cd[k][u]<cd[k][v]))
	v =u;
    }
    if(v ==-1)
      break;
    used[v] =1;
   
    for(int u = 0;u <n;u++){
      if(used[u] ==-1){
      if(k ==0){
	cd[k][u] =min(cd[k][u],cd[k][v]+cost[v][u]);
      }
      else{
	cd[k][u] = min(cd[k][u],min(cd[k][v]+cost[v][u],cd[k-1][v]+cost[v][u]/2));
      }
      }
    }
    }
  }
}
int main()
{
  int s;
  while(cin >>c>>n>>m>>s>>d){
    if(c+n+m+s+d ==0)
      break;
  for(int i = 0;i <n;i++){
    for(int j = 0;j < n;j++){
      if(i !=j)
	cost[i][j] =INF;
      else
	cost[i][j] = 0;
    }
  }
  for(int i = 0;i < m;i++){
    cin >>a>>b>>f;
    cost[a-1][b-1] = f;
    cost[b-1][a-1] = f;
  }
  dijkstra(s-1);
  cout <<cd[c][d-1]<<endl;
  }
  return 0;
}