#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

const int INF = 1<<28;
int c, n, m, s, d;
vector<pair<int, int> > g[100];
int dist[100][11];

typedef tuple<int, int, int> node;

int dijkstra() {
  priority_queue<node, vector<node>, greater<node> > Q;
  Q.push(make_tuple(0, s, c));
  dist[s][c] = 0;
  
  while (!Q.empty()) {
    int cost;
    int v;
    int t;
    tie(cost, v, t) = Q.top();
    Q.pop();
    for (auto &edge: g[v]) {
      int w = edge.first;
      int weight = edge.second;
      if (cost + weight < dist[w][t]) {
        dist[w][t] = cost + weight;
        Q.push(make_tuple(dist[w][t], w, t));
      }
      if (t > 0 && cost + weight/2 < dist[w][t-1]) {
        dist[w][t-1] = cost + weight/2;
        Q.push(make_tuple(dist[w][t-1], w, t-1));
      }
    }
  }

  int ret = INF;
  for (int i = 0; i < 11; i++)
    ret = min(ret, dist[d][i]);
  return ret;
}

void init() {
  for (int i = 0; i < 100; i++)
    g[i].clear();
  for (int i = 0; i < 100; i++)
    for (int j = 0; j < 11; j++)
      dist[i][j] = INF;
}

int main(int argc, char *argv[])
{
  for (;;) {
    cin >> c >> n >> m >> s >> d;
    if (!c && !n && !m && !s && !d)
      break;
    --s, --d;
    init();
    for (int i = 0; i < m; i++) {
      int a, b, f;
      cin >> a >> b >> f;
      --a, --b;
      g[a].push_back(make_pair(b, f));
      g[b].push_back(make_pair(a, f));
    }
    int ret = dijkstra();
    printf("%d\n", ret);
  }
  
  return 0;
}