#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

typedef pair<int, int> Pair;

int main() {
  int c, n, m, s, d, a, b, f;
  unsigned long long answer;
  vector<Pair> edges[1100];
  unsigned long long min_cost[1100];
  priority_queue<Pair, vector<Pair>, greater<Pair> > heap;
  while (true) {
    cin >> c >> n >> m >> s >> d;
    if (c == 0) {
      return 0;
    }
    for (int i = 0; i < (c + 1) * n; ++i) {
      edges[i].clear();
      min_cost[i] = -1;
    }
    for (int i = 0; i < m; ++i) {
      cin >> a >> b >> f;
      for (int ci = 0; ci <= c; ++ci) {
        edges[a - 1 + ci * n].push_back(Pair(b - 1 + ci * n, f));
        edges[b - 1 + ci * n].push_back(Pair(a - 1 + ci * n, f));
        if (ci < c) {
          edges[a - 1 + ci * n].push_back(Pair(b - 1 + ci * n + n, f / 2));
          edges[b - 1 + ci * n].push_back(Pair(a - 1 + ci * n + n, f / 2));
        }
      }
    }
    heap.push(Pair(0, s - 1));
    min_cost[s - 1] = 0;
    while (not heap.empty()) {
      int p1 = heap.top().second;
      heap.pop();
      for (size_t i = 0; i < edges[p1].size(); ++i) {
        int p2 = edges[p1][i].first;
        int len = edges[p1][i].second;
        if (min_cost[p1] + len < min_cost[p2]) {
          min_cost[p2] = min_cost[p1] + len;
          heap.push(Pair(min_cost[p2], p2));
        }
      }
    }
    answer = min_cost[d - 1];
    for (int ci = 1; ci <= c; ++ci) {
      answer = min(answer, min_cost[d - 1 + n * ci]);
    }
    cout << answer << endl;
  }
}