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

#define fr first
#define sc second
typedef pair<int,int> Pi;
typedef pair<Pi,int> Pii;
struct edge{
  int to,cost;
};
typedef vector< vector< edge > > Graph;

int Dijkstr(Graph& info,int s,int g,int c){
  vector< vector<int> > min_cost;
  priority_queue<Pii,vector<Pii>,greater<Pii> > que;
  min_cost.resize(c+1,vector<int>(info.size(),-1)); //min_costの確保と共に、全てに-1を代入。
  
  que.push( Pii(Pi(0,s),c) ); //fr:現在額。sc:現在地。
  min_cost[c][s] = 0;
  while(!que.empty()){
    Pii p = que.top();//fr.fr:現在額。fr.sc:現在地。sc:割引券。
    que.pop();
    if(p.fr.sc == g) return p.fr.fr;
    if(p.fr.fr > min_cost[p.sc][p.fr.sc]) continue; //最も小さな値より大きい時はまわらない。
    for(int i=0;i<info[p.fr.sc].size();i++){ //p.scから伸びる道の数だけまわる。
      edge& e = info[p.fr.sc][i];//p.scから伸びる道の一つ。
      if(min_cost[p.sc][e.to] == -1 || p.fr.fr+e.cost < min_cost[p.sc][e.to]){//まだ行っていないか、いままでで一番安いか。
	min_cost[p.sc][e.to] = p.fr.fr+e.cost;//min_costを更新。
	que.push( Pii(Pi(min_cost[p.sc][e.to],e.to),p.sc));//移動後を現在額と現在値として記録。
      }
      if(p.sc > 0 && (min_cost[p.sc-1][e.to] == -1 || p.fr.fr+(e.cost/2) < min_cost[p.sc-1][e.to])){
	min_cost[p.sc-1][e.to] = p.fr.fr+e.cost/2;//min_costを更新。
	que.push( Pii(Pi(min_cost[p.sc-1][e.to],e.to),p.sc-1));//移動後を現在額と現在値として記録。
      }
    }
  }
  
  return -1;
}


int main(){
  int c,n,m,s,d;
  while(1){
    Graph info;
    cin >> c >> n >> m >> s >> d;
    if(c==0 && n==0 && m==0 && s==0 && d==0) break;
    info.resize(m + 1);
    int a,b,f;
    for(int i=0;i<m;i++){
      cin >> a >> b >> f;
      info[a].push_back((edge){b,f});
      info[b].push_back((edge){a,f});
    }
    
    //経路探索
    cout << Dijkstr(info,s,d,c) << endl;
  }
}