#include <iostream>
#include <queue>
#include <algorithm>
#define INF 9999999
using namespace std;

class State {
public:
  int id;
  int cost;
  int tiket;
  bool operator <(const State &s) const {
    if(tiket != s.tiket) return tiket < s.tiket;
    return cost > s.cost;
  }
  State(int id, int cost, int tiket) : id(id), cost(cost), tiket(tiket) {}
};

int main() {
  while(1) {
    int c, n, m, s, d;
    cin >> c >> n >> m >> s >> d;
    if(c == 0 && n == 0 && m == 0 && s == 0 && d == 0) break;
    int data[n+1][n+1];
    fill(&data[0][0], &data[n][n]+1, INF);
    for(int i = 0; i < m; i++) {
      int a, b, f;
      cin >> a >> b >> f;
      data[a][b] = data[b][a] = f;
    }

    priority_queue<State> PQ;
    PQ.push(State(s, 0, c));
    bool visited[n+1][c+1];
    int cost[n+1][c+1];
    fill(&visited[0][0], &visited[n][c] + 1, false);
    fill(&cost[0][0], &cost[n][c] + 1, INF);
    cost[s][c] = 0;
    while(!PQ.empty()) {
      State s = PQ.top();
      PQ.pop();
      visited[s.id][s.tiket] = true;
      for(int i = 1; i <= n; i++) {
	if(!visited[i][s.tiket] && data[s.id][i] != INF) {
	  int newValue = cost[s.id][s.tiket] + data[s.id][i];
	  if(newValue < cost[i][s.tiket]) {
	    cost[i][s.tiket] = newValue;
	    PQ.push(State(i, newValue, s.tiket));
	  }
	}
	if(s.tiket >= 1 && !visited[i][s.tiket-1] && data[s.id][i] != INF) {
	  int newValue = cost[s.id][s.tiket] + data[s.id][i]/2;
	  if(newValue < cost[i][s.tiket-1]) {
	    cost[i][s.tiket-1] = newValue;
	    PQ.push(State(i, newValue, s.tiket-1));
	  }
	}
      }
    }
    int min = INF;
    for(int i = 0; i <= c; i++) {
      if(cost[d][i] < min) min = cost[d][i];
    }
    cout << min << endl;
  }
  return 0;
}