#include <iostream>

#define MX 1000000000

using namespace std;
int cost[100][100],n;

int dijkstra(int s , int g , int c){
  bool visited[100];
  int d[100][11];
  for(int i=0;i <= c;i++){
    for(int j=0;j < n;j++) d[j][i] = MX , visited[j] = false;
    d[s][i] = 0;
      while(1){
        int u;
        int mincost = MX;
        for(int j=0;j<n;j++)if(!visited[j] && d[j][i] < mincost) mincost = d[j][i],u = j;
        if(mincost == MX) break;
        visited[u] = true;
        for(int v = 0;v < n;v++){
          if(visited[v] || cost[u][v] == MX) continue;
          if(d[v][i] > d[u][i] + cost[u][v]) d[v][i] = d[u][i] + cost[u][v];
          if(i > 0) if(d[v][i] > d[u][i-1] + cost[u][v] / 2) d[v][i] = d[u][i-1] + cost[u][v] / 2;
        }
      }
  }
  return d[g][c];
}

int main(){
  int c,m,s,d;
  while(cin >> c >> n >> m >> s >> d && (c|n|m|s|d)){
    for(int i=0;i<n;i++)for(int j=0;j<n;j++) cost[i][j] = MX;
    while(m--){
      int a,b;
      cin >> a >> b;
      cin >> cost[a-1][b-1];
      cost[b-1][a-1] = cost[a-1][b-1];
    }
    cout << dijkstra(s-1,d-1,c) << endl;
  }
  return 0;
}