#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

struct edge { int to,cost; };
typedef pair<int,int> P;
typedef pair<int,P> PP;

#define INF (1<<30)
int main(){
  int c,n,m,s,d;
  int a,b,f;
  edge e;
  int ans = INF;
  while(1){
    cin >> c >> n >> m >> s >> d;
    if(c == 0 && n == 0 && m == 0 && s == 0 && d == 0)break;
    vector<edge> G[101];
    int min_cost[101][20];
    for(int i=0;i<=n;i++){
      for(int j=0;j<=c+1;j++){
	min_cost[i][j] = INF;
      }
    }
    for(int i=0;i<m;i++){
      cin >> a >> b >> f;
      e.to = b;
      e.cost = f;
      G[a].push_back(e);
      e.to = a;
      e.cost = f;
      G[b].push_back(e);
    }
    
    priority_queue<PP,vector<PP>,greater<PP> > que;
    min_cost[s][c] = 0;
    que.push(PP(0,P(s,c)));
    while(!que.empty()){
      PP p;
      p = que.top();
      que.pop();
      int now = p.second.first;
      int tick = p.second.second;
      if(min_cost[now][tick] < p.first) continue;
      for(int i=0;i<G[now].size();i++){
	edge e = G[now][i];
	if(min_cost[e.to][tick] > min_cost[now][tick] + e.cost){
	  min_cost[e.to][tick] = min_cost[now][tick] + e.cost;
	  que.push(PP(min_cost[e.to][tick],P(e.to,tick)));
	}
	if( tick ){
	  if(min_cost[e.to][tick-1] > min_cost[now][tick] + e.cost / 2){
	    min_cost[e.to][tick-1] = min_cost[now][tick] + e.cost / 2;
	    que.push(PP(min_cost[e.to][tick-1],P(e.to,tick-1)));
	  }
	}
      }
    }
    ans = INF;
    for(int i=0;i<c+1;i++){
      if(ans > min_cost[d][i]){
	ans = min_cost[d][i];
      }
    }
    cout << ans << endl;
  }
}