#include <iostream>
#include <queue>
#define INF (1e9)
#define N 101
#define C 11
using namespace std;
void dijkstra(int);
int M[N][N],d[N][C],c,n;
typedef struct data{
  int cost,pos,ticket;
  bool operator<(const data & right)const{
    return cost > right.cost;
  }
} data;
int main(){
  int m,s,id,a,b,f;
  while(1){
    cin >> c >> n >> m >> s >> id;
    if(c==0&&n==0&&m==0&&s==0&&id==0) break;
    for(int i=0;i<=n;i++)
      for(int j=0;j<=n;j++)
	M[i][j]=INF;
    for(int i=0;i<m;i++){
      cin >> a >> b >> f;
      M[a][b]=M[b][a]=f;
    }
    dijkstra(s);
    cout << d[id][c] << endl;
  }
  return 0;
}
void dijkstra(int s){
  priority_queue<data> q;
  for(int i=1;i<=n;i++)
    for(int j=0;j<=c;j++)
      d[i][j]=INF;
  d[s][0]=0;
  q.push((data){0,s,0});
  while(!q.empty()){
    data t=q.top();
    q.pop();
    int cost=t.cost,pos=t.pos,ticket=t.ticket;
    if(d[pos][ticket]>cost) continue;
    for(int i=1;i<=n;i++){
      if(d[i][ticket]>d[pos][ticket]+M[pos][i]){
	d[i][ticket]=d[pos][ticket]+M[pos][i];
	q.push((data){d[i][ticket],i,ticket});
      }
      if(ticket==c) continue;
      if(d[i][ticket+1]>d[pos][ticket]+M[pos][i]/2){
	d[i][ticket+1]=d[pos][ticket]+M[pos][i]/2;
	q.push((data){d[i][ticket+1],i,ticket+1});
      }
    }
  }
}