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

class State{
public:
  int id, rem, cost;

  State(int _id, int _rem, int _cost){
    id = _id;
    rem = _rem;
    cost = _cost;
  }

  bool operator<(const State &st)const{
    return cost > st.cost;
  }
};

int c, n, m, s, d;
bool closed[102][12];
int t[102][102];

void solve(){
  priority_queue<State> open;
  memset(closed, 0, sizeof(closed));
  open.push(State(s, c, 0));

  while(!open.empty()){
    State st = open.top(); open.pop();
    if(closed[st.id][st.rem]) continue;
    closed[st.id][st.rem] = true;

    if(st.id == d){
      cout << st.cost << endl;
      return;
    }

    for(int i = 0; i < n; i++){
      if(t[st.id][i] != -1){
        open.push(State(i, st.rem, st.cost + t[st.id][i]));
        if(st.rem > 0){
          open.push(State(i, st.rem - 1, st.cost + t[st.id][i] / 2));
        }
      }
    }
  }
}

int main(){
  while(cin >> c >> n >> m >> s >> d, c || n || m || s || d){
    s--;
    d--;

    memset(t, -1, sizeof(t));

    for(int i = 0; i < m; i++){
      int a, b, f;
      cin >> a >> b >> f;
      a--;
      b--;
      t[a][b] = t[b][a] = f;
    }

    solve();
  }
}