#include <iostream>
#include <vector>
#include <queue>
#define INF (1e9)
#define N 101
#define C 11
using namespace std;

typedef struct state {
  int cost,pos,ticket;
  state (int a,int b,int c): cost(a),pos(b),ticket(c){} 
  bool operator < (const state &s)const{
    return cost > s.cost;
  }
} state;

void dijkstra(int);
int c,n,d[N][C],M[N][N];
int main(){
  int m,s,ind,a,b,f;
  while(1){
    cin >> c >> n >> m >> s >> ind;
    if(c==0&&n==0&&m==0&&s==0&&ind==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[ind][c] << endl;
  }
  return 0;
}
void dijkstra(int s){
  priority_queue< state > q;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=c;j++)
      d[i][j]=INF;
  d[s][0]=0;
  q.push( (state){0,s,0} );
  while(!q.empty()){
    state r=q.top();
    q.pop();
    int cos=r.cost;
    pair<int,int> u=make_pair(r.pos,r.ticket);
    if(d[u.first][u.second]<cos) continue;
    for(int i=1;i<=n;i++){
      if(d[u.first][u.second]!=INF&&M[u.first][i]!=INF){
	if(d[i][u.second]>d[u.first][u.second]+M[u.first][i]){
	  d[i][u.second]=d[u.first][u.second]+M[u.first][i];
	  q.push((state){d[i][u.second],i,u.second});
	}
	if(u.second+1<=c&&d[i][u.second+1]>d[u.first][u.second]+M[u.first][i]/2){
	  d[i][u.second+1]=d[u.first][u.second]+M[u.first][i]/2;
	  q.push((state){d[i][u.second+1],i,u.second+1});
	}
      }
    }
  }
}