#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#define INF (1<<21)
using namespace std;

class State{
public:
  int n,cost,c,f;
  State(int n = 0,int cost = 0, int c = 0,int f = 0):n(n),cost(cost),c(c),f(f){}
  bool operator < (const State &s) const{ return cost > s.cost;}
};

int main(){
  int i,j;
  while(1){
    int G[101][101],c,n,m,s,t;
    State d[101][11];
    priority_queue<State> PQ;

    cin >> c >> n >> m >> s >> t;
    if(c == 0 && n == 0 && m == 0 && s == 0 && t == 0) break;

    for(i=0;i<=n;i++){
      for(j=0;j<=n;j++) G[i][j] = INF;
      for(j=0;j<=c;j++){
	d[i][j].cost = INF;
	d[i][j].n = i;
	d[i][j].c = j;
	d[i][j].f = 0;
      }
    }

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

    d[s][c].cost = 0;
    State p = d[s][c];
    PQ.push(p);

    while(!PQ.empty()){
      p = PQ.top();
      PQ.pop();
      d[p.n][p.c].f = 1;

      for(i=0;i<=n;i++){
	if(d[i][p.c].f == 0 && G[p.n][i] + p.cost < d[i][p.c].cost){
	  d[i][p.c].cost = G[p.n][i] + p.cost;
	  PQ.push(d[i][p.c]);
	}
	if(p.c > 0 && G[p.n][i] != INF && d[i][p.c-1].f == 0 && G[p.n][i] / 2 + p.cost < d[i][p.c-1].cost){
	  d[i][p.c-1].cost = G[p.n][i] / 2 + p.cost;
	  PQ.push(d[i][p.c-1]);
	}
      }
    }

    int min = INF;
    for(i=0;i<=c;i++){
      if(min > d[t][i].cost) min = d[t][i].cost;
    }
    cout << min << endl;

  }
  return 0;
}

//0212