#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define INF (1<<24)

struct state{
  int cost,pos,cnt;
  bool operator < (const state &p) const{
    return cost>p.cost;
  }
};

struct edge{
  int to,cost;
};

int c,n,m,s,d;
vector<edge> G[100];

void init(){
  for(int i=0;i<100;i++)G[i].clear();
}

int dijkstra(int si,int ti){
  int d[100][11];
  for(int i=0;i<100;i++)
    for(int j=0;j<11;j++)d[i][j]=INF;

  d[si][c]=0;
  priority_queue< state > Q;
  Q.push((state){0,si,c});

  while(!Q.empty()){
    state s=Q.top();Q.pop();
    if(s.cost>d[s.pos][s.cnt])continue;

    for(int i=0;i<(int)G[s.pos].size();i++){
      edge e=G[s.pos][i];
      if(s.cost+e.cost>=d[e.to][s.cnt])continue;
      d[e.to][s.cnt]=s.cost+e.cost;
      Q.push((state){s.cost+e.cost,e.to,s.cnt});
    }

    if(s.cnt==0)continue;

    for(int i=0;i<(int)G[s.pos].size();i++){
      edge e=G[s.pos][i];
      if(s.cost+e.cost/2>=d[e.to][s.cnt-1])continue;
      d[e.to][s.cnt-1]=s.cost+e.cost/2;
      Q.push((state){s.cost+e.cost/2,e.to,s.cnt-1});
    }
  }//while

  int res=INF;
  for(int i=0;i<=c;i++){
    res=min(res,d[ti][i]);
  }
  return res;
}

int main(){
  int a,b,f;
  while(cin>>c>>n>>m>>s>>d){
    if(n==0)break;
    init();
    for(int i=0;i<m;i++){
      cin>>a>>b>>f;
      a--;b--;
      G[a].push_back((edge){b,f});
      G[b].push_back((edge){a,f});
    }
    cout<<dijkstra(s-1,d-1)<<endl;
  }
  return 0;
}