#include<iostream>
#include<vector>
#include<queue>
using namespace std;

typedef struct edge{
  int to, cost;
}edge;

using pii = pair<int, int>;
using piii = pair<int, pii>;//cost, c, pos

int main(){
  int c, n, m, s, d;
  while(std::cin >> c >> n >> m >> s >> d){
    if(c == 0)break;
    s--, d--;
    vector<vector<edge> > G(n);
    for (int i = 0; i < m; i++) {
      int a, b, f;
      std::cin >> a >> b >> f;
      a--, b--;
      G[a].push_back((edge){b, f});
      G[b].push_back((edge){a, f});
    }
    priority_queue<piii, vector<piii>, greater<piii> > que;
    que.push(piii(0, pii(c, s)));
    vector<vector<int> > dist(c + 1, vector<int>(n, 1e9));
    dist[c][s] = 0;
    while(not que.empty()){
      int cc = que.top().first;
      int remain = que.top().second.first;
      int v = que.top().second.second;
      // std::cout << cc << " " << remain << " " << v << std::endl;
      que.pop();
      for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i].to;
        int add = G[v][i].cost;
        // std::cout << u << std::endl;
        if(dist[remain][u] > cc + add){
          dist[remain][u] = cc + add;
          que.push(piii(cc + add, pii(remain, u)));
        }
        if(remain > 0 and dist[remain - 1][u] > cc + add/2){
          dist[remain - 1][u] = cc + add/2;
          que.push(piii(cc + add/2, pii(remain - 1, u)));
        }
      }
    }
    int ans = 1e9;
    for (int i = 0; i <= c; i++) ans = min(ans, dist[i][d]);
    std::cout << ans << std::endl;
  }
  return 0;
}

