#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
struct edge{int to,cost;};
typedef pair<int,int>P;
typedef pair<int,P>P2;
int c,n,m,s,d,a1,a2,a3,dis[102][11];
vector<edge>v[102];
int main(){
  while(cin>>c>>n>>m>>s>>d,c){
    r(i,102)r(j,11)dis[i][j]=1e8;
    r(i,102)v[i].clear();
    r(i,m){
      cin>>a1>>a2>>a3;
      v[a1].push_back(edge{a2,a3});
      v[a2].push_back(edge{a1,a3});
    }
    priority_queue<P2,vector<P2>,greater<P2> >q;
    q.push(P2(0,P(s,c)));
    dis[s][c]=0;
    while(!q.empty()){
      P2 p=q.top();q.pop();
      int now=p.second.first;
      int card=p.second.second;
      int len=p.first;
      if(dis[now][card]<len)continue;
      r(i,v[now].size()){
        int next=v[now][i].to;
        int cost2=v[now][i].cost;
        if(dis[next][card]>cost2+len){
          dis[next][card]=cost2+len;
          q.push(P2(cost2+len,P(next,card)));
        }
        if(card&&dis[next][card-1]>cost2/2+len){
          dis[next][card-1]=cost2/2+len;
          q.push(P2(cost2/2+len,P(next,card-1)));
        }
      }
    }
    int ans=1e9;
    r(i,11)ans=min(ans,dis[d][i]);
    cout<<ans<<endl;
  }
}