#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

int c, n, m, s, d;

struct N {
  int cost, ticket, stop;
  bool operator < (const N &t)const {
    return cost > t.cost;
  }
  N(int cost, int ticket, int stop) :
    cost(cost), ticket(ticket), stop(stop){}
  void print() {
    printf("cost = %d, ticket = %d, stop = %d\n", cost, ticket, stop);
  }
};

typedef vector<pair<int , int> > edge;

edge G[100];
int visited[100][11];

const int MAX = INT_MAX;

int solve()
{
  for (int i = 0; i < 100; i++) {
    fill(visited[i], &visited[i][11], MAX);
  }
  priority_queue<N> Q;
  Q.push(N(0, c, s));
      
  //printf("ok\n");  
      
  while (true) {    
    N cur = Q.top();
    Q.pop();

    //cur.print();
    int cc = cur.cost, ct = cur.ticket, cs = cur.stop;
    if (cs == d) {
      return cc;
    }

    for (int i = 0; i < G[cs].size(); i++) {
      int t = G[cs][i].first, ec = G[cs][i].second;
      if (cc + ec < visited[t][ct]) {
        visited[t][ct] = cc + ec;
        Q.push(N(visited[t][ct], ct, t));
      }
      if (ct > 0 && cc + ec / 2 < visited[t][ct - 1]) {
        visited[t][ct - 1] = cc + ec / 2;
        Q.push(N(visited[t][ct - 1], ct - 1, t));
      }
    }
  }                
}

int main()
{
  while (scanf("%d %d %d %d %d ", &c, &n, &m, &s, &d) == 5) {
    if (c == 0 && n == 0 && m == 0 && s == 0 && d == 0) {
      break;
    }
    s--, d--;
    for (int i = 0; i < n; i++) {
      G[i].clear();
    }
    for (int i = 0; i < m; i++) {
      int a, b, cost;
      scanf("%d %d %d ", &a, &b, &cost);
      //printf("%d %d %d\n", a, b, cost);
      a--, b--;
      G[a].push_back(make_pair(b, cost));
      G[b].push_back(make_pair(a, cost));
    }
    /*for (int i = 0; i < n; i++) {
      for (int j = 0; j < G[i].size(); j++) {
        printf("%d %d: %d\n", i, G[i][j].first, G[i][j].second);
      }
      }*/
    printf("%d\n", solve());
  }
  return 0;
}