#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> PP;
int graph[110][110];
int c,n,m,s,d;
int D[110][15];
const int INF = 1<<28;

void Init(){
  for(int i=0;i<110;i++){
    for(int k=0;k<110;k++){
      graph[i][k] = INF;
    }
    for(int j=0;j<15;j++){
      D[i][j] = INF;
    }
  }

}


void dijkstra(){
  priority_queue<PP,vector<PP>,greater<PP> > que;
  D[s][c] = 0;
  // PP( P(pos,cost), c )
  // .F.F -> pos
  // .F.S -> cost
  // .S   -> c
  que.push(PP(P(s,0),c));
  while(!que.empty() ){
    PP p = que.top();que.pop();
    int v = p.F.F;
    for(int i=1;i<=n;i++){
     
      if(D[i][p.S] > graph[v][i] + p.F.S){
	D[i][p.S] = graph[v][i] + p.F.S;
	que.push(PP(P(i,D[i][p.S]),p.S));
      }

      if(D[i][p.S-1] > graph[v][i]/2 + p.F.S && p.S != 0){
	D[i][p.S-1] = graph[v][i]/2 + p.F.S;
	que.push(PP(P(i,D[i][p.S-1]),p.S-1));
      }


    }


  }

}

int main(){
  int x,y,co;
  while(true){
    cin >> c >> n >> m >> s >> d;
    if(c+n+m+s+d == 0)break;
    Init();

    for(int i=0;i<m;i++){
      cin >> x >> y >> co;
      graph[x][y] = graph[y][x] = co;
    }


    dijkstra();
    int ans = INF;
    for(int i=0;i<=c;i++)ans = min(ans,D[d][i]);
    cout<< ans << endl;
  }
  return 0;
}


//Version.2