#include<bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

struct Edge{
  int to,cost;
};

struct Node{
  int val,num;
};

struct P{
  int val,num,c;
  bool operator<(const P &r)const{
    return val < r.val;
  }
};




int main(){
  int c,n,m,s,d;
  
  while(1){
  cin >> c >> n >> m >> s >> d;
  s--;d--;
  if(c == 0 && n == 0 && m == 0 && s == -1 && d == -1)break;
  vector<Edge>edge[105];
  Node node[11][105];
  
  priority_queue<P> que;
  for(int i = 0; i < m; i++){
    int a,b,c;
    cin >> a >> b >> c;
    a--;b--;
    edge[a].push_back((Edge){b,c});
    edge[b].push_back((Edge){a,c});
  }


  for(int i = 0; i < 11; i++){
    for(int j = 0; j < n; j++){
      node[i][j].val = INF;
      node[i][j].num = j;
    }
  }

  node[c][s].val = 0;
  
  que.push((P){0,s,c});

  while(!que.empty()){
    int val = que.top().val;
    int now = que.top().num;
    int ticket = que.top().c;
    que.pop();
  
    if(ticket){
      for(int i = 0; i < edge[now].size(); i++){
	int next = edge[now][i].to;
	int cost = edge[now][i].cost;

	if(node[ticket - 1][next].val > node[ticket][now].val + cost / 2){
	  node[ticket - 1][next].val = node[ticket][now].val + cost / 2;
	  que.push((P){node[ticket - 1][next].val,next,ticket - 1});
	}
      } 
    }

    for(int i = 0; i < edge[now].size(); i++){
      int next = edge[now][i].to;
      int cost = edge[now][i].cost;
      
      if(node[ticket][next].val > node[ticket][now].val + cost){
	node[ticket][next].val = node[ticket][now].val + cost;
	que.push((P){node[ticket][next].val,next,ticket});
      }
    }
  }
  
  int ans = INF;

  for(int i = 0; i < c; i++){
    ans = min(ans,node[i][d].val);
  }

  cout << ans << endl;
  }
}
  