#include <iostream>
#include <algorithm>

  using namespace std;

  const int INF = 1000000000;

  int c, n, m, s, d;
  int visited[100][11];
  int edge[100][100];

  void dfs(int p, int rem, int cost){
    if(visited[p][rem] < cost) return;
    visited[p][rem] = cost;
    if(p == d) return;
    for(int i=0;i<n;i++){
      if(edge[p][i] == INF) continue;
      if(rem > 0 ) dfs(i, rem-1, cost+(edge[p][i]/2));
      dfs(i, rem, cost+edge[p][i]);
    }
  }


 main(){
    while(cin >> c >> n >> m >> s >> d && (c || n || m || s || d)){
      fill(edge[0], edge[100], INF);
      fill(visited[0], visited[100], INF);
      --s; --d;
      for(int i=0;i<m;i++){
         int a, b, f;
         cin >> a >> b >> f;
         --a; --b;
         edge[a][b] = edge[b][a] = f;
      }

      dfs(s, c, 0);
      int ans = INF;
      for(int i=0;i<c;i++){
         ans = min(ans, visited[d][i]);
      }

      cout << ans << endl;
    }

    return 0;
} 