#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
using CostType = long long int;
const CostType INF = 1LL << 60;

struct Elem {
  CostType pos, tic, cost;
  Elem(CostType a, CostType b, CostType c) : pos(a), tic(b), cost(c) {}
  bool operator<(const Elem &e) const {
    return cost > e.cost;
  }
};

int solve() {
  CostType rec[110][15];
  vector< pair<int, int> > G[110];
  
  int C, N, M, S, D; cin >> C >> N >> M >> S >> D;
  if(C == 0) return 1;
  
  for(int i=0; i<N; i++) G[i].clear();
  
  for(int i=0; i<M; i++) {
    CostType u, v, cost; cin >> u >> v >> cost;
    u--; v--;
    G[u].emplace_back(v, cost);
    G[v].emplace_back(u, cost);
  }

  S--; D--;
  priority_queue<Elem> que;
  fill(rec[0], rec[N+1], INF);
  rec[S][0] = 0;
  que.emplace(S, 0, 0);

  while(que.size()) {
    auto cur = que.top(); que.pop();
    if(cur.cost > rec[cur.pos][cur.tic]) continue;
    CostType mon = cur.cost;
    for(auto e : G[cur.pos]) {
      CostType u = cur.pos, v = e.first, c = e.second;
      if(cur.tic + 1 <= C) {
        int nt = cur.tic + 1, nc = mon + c / 2;
        if(rec[v][nt] > nc) {
          rec[v][nt] = nc;
          que.emplace(v, nt, nc);
        }
      }

      {
        int nt = cur.tic, nc = mon + c;
        if(rec[v][nt] > nc) {
          rec[v][nt] = nc;
          que.emplace(v, nt, nc);
        }
      }
    }
  }

  CostType ans = INF;
  for(int i=0; i<=C; i++) {
    ans = min(ans, rec[D][i]);
  }
  cout << ans << endl;
  return 0;
}

int main() {
  while(!solve());
}

