
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<climits>
using namespace std;

struct Data{
  int id;
  int cost;
  int ticket;
};
bool operator<(Data a, Data b){
  return a.cost!=b.cost?a.cost>b.cost:(a.ticket!=b.ticket?a.ticket<b.ticket:a.id>b.id);
}
struct Data2{
  int id;
  int ticket;
};
bool operator<(Data2 a, Data2 b){
  return a.id!=b.id?a.id>b.id:a.ticket<b.ticket;
}

#define NONE INT_MAX

int Dijkstra(vector< vector<int> >A,int start,int goal,int ticket)
{
  vector<int>cost(A.size(),NONE);
  priority_queue<Data>q;
  set<Data2>used;

  Data node={start,0,ticket};
  q.push(node);
  cost[start]=0;

  while(q.size()){
    node=q.top();q.pop();
    if(node.id==goal)return node.cost;
    Data2 t={node.id,node.ticket};
    if(used.count(t))continue;
    used.insert(t);
    for(int i=0;i<A[node.id].size();i++){
      if(A[node.id][i]==NONE)continue;
      if(node.ticket){
	if(cost[i]>cost[node.id]+(A[node.id][i])/2){
	  Data next={i,cost[node.id]+(A[node.id][i])/2,node.ticket-1};
	  cost[i]=next.cost;
	  q.push(next);
	}
      }
      if(cost[i]<=cost[node.id]+A[node.id][i])continue;
      Data next={i,cost[node.id]+A[node.id][i],node.ticket};
      cost[i]=next.cost;
      q.push(next);
    }
  }
  return -1;
}

int main()
{
  int c,n,m,s,d;
  int a,b,f;
  while(cin>>c>>n>>m>>s>>d,c|n|m|s|d){
    s--;d--;
    vector< vector<int> >A(n,vector<int>(n,NONE));
    for(int i=0;i<m;i++){
      cin>>a>>b>>f;
      a--;b--;
      A[a][b]=A[b][a]=f;
    }
    cout<<Dijkstra(A,s,d,c)<<endl;
  }
}