#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct edge {
  int from, to, cost;
  edge(int f = -1, int t = -1, int c = 0) : from(f), to(t), cost(c) {}
};

int c, n, m, s, d;
int dis[110][11];
vector<edge> g[110];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  while (cin >> c >> n >> m >> s >> d, c) {
    s--, d--;
    for (int i = 0; i < n; i++) g[i].clear();
    for (int i = 0; i < m; i++) {
      int a, b, f;
      cin >> a >> b >> f;
      a--, b--;
      g[a].emplace_back(a, b, f);
      g[b].emplace_back(b, a, f);
    }
    fill_n((int*)dis, 110 * 11, 1 << 30);
    dis[s][c] = 0;
    using P = tuple<int, int, int>;
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(0, s, c);
    while (!que.empty()) {
      P u = que.top(); que.pop();
      int dist, curr, tic;
      tie(dist, curr, tic) = u;
      if (dist > dis[curr][tic]) continue;
      for (auto e : g[curr]) {
        int next = e.to;
        if (dis[next][tic] > dis[curr][tic] + e.cost) {
          dis[next][tic] = dis[curr][tic] + e.cost;
          que.emplace(dis[next][tic], next, tic);
        }
        if (tic > 0 && dis[next][tic - 1] > dis[curr][tic] + e.cost / 2) {
          dis[next][tic - 1] = dis[curr][tic] + e.cost / 2;
          que.emplace(dis[next][tic - 1], next, tic - 1);
        }
      }
    }
    int ans = 1 << 30;
    for (int i = 0; i <= c; i++) {
      ans = min(ans, dis[d][i]);
    }
    cout << ans << endl;
  }

  return 0;
}
