#include<bits/stdc++.h>
using namespace std;
struct NODE{
  int to,cost,tick;
  NODE(int to,int cost,int tick) : to(to),cost(cost),tick(tick){}
  NODE(){}
  bool operator < (const NODE &a)const{
    return cost > a.cost;
  }
};
int main(){
  int c,n,m,s,d,a,b,f;
  while(cin>>c>>n>>m>>s>>d&&c&&n&&m&&s&&d){
    vector<NODE> edge[101];
    
    for(int i=0;i<m;i++){
      cin >> a >> b >> f;
      edge[a].push_back(NODE(b,f,-1));
      edge[b].push_back(NODE(a,f,-1));
    }
    bool done[101][20] = {};
    priority_queue<NODE> Q;
    Q.push(NODE(s,0,c));
    while(!Q.empty()){
      NODE q = Q.top();Q.pop();
      if(done[q.to][q.tick] == true)continue;
      done[q.to][q.tick] = true;
      if(q.to == d){
	cout << q.cost << endl;
	break;
      }
      for(int i=0;i<edge[q.to].size();i++){
	Q.push(NODE(edge[q.to][i].to,q.cost + edge[q.to][i].cost,q.tick));
	if(q.tick){
	  Q.push(NODE(edge[q.to][i].to,q.cost + (edge[q.to][i].cost/2),q.tick-1));
	}
      }
    }
  }
}