#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

const int INF = (int)1e9;

struct Edge {
  int src, dst, cost;
  Edge(int src_, int dst_, int cost_) : src(src_), dst(dst_), cost(cost_) { }
};

int main() {
  for(int C, N, M, S, T; cin >> C >> N >> M >> S >> T, C || N || M || S || T; ) {
    --S, --T;
    vector<Edge> G;
    for(int i = 0; i < M; ++i) {
      int a, b, f; cin >> a >> b >> f;
      --a, --b;
      G.emplace_back(a, b, f);
      G.emplace_back(b, a, f);
    }
    int D[N][C + 1];
    for(int i = 0; i < N; ++i)
      for(int j = 0; j <= C; ++j)
        D[i][j] = INF;
    D[S][C] = 0;
    while(true) {
      bool update = false;
      for(const Edge &e : G) {
        for(int j = 0; j <= C; ++j) {
          if(D[e.dst][j] > D[e.src][j] + e.cost) {
            D[e.dst][j] = D[e.src][j] + e.cost;
            update = true;
          }
          if(j > 0 && D[e.dst][j - 1] > D[e.src][j] + e.cost / 2) {
            D[e.dst][j - 1] = D[e.src][j] + e.cost / 2;
            update = true;
          }
        }
      }
      if(!update) break;
    }
    int ans = INF;
    for(int j = 0; j <= C; ++j) {
      ans = min(ans, D[T][j]);
    }
    cout << ans << endl;
  }
}