#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<map>
#define INF (1<<20)
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> PP;
struct edge{ int to,cost;};
int C,N,M,S,D;
vector<edge> G[111];
int minc[111][11];
void solve(){
  memset(minc,-1,sizeof(minc));
  priority_queue< PP,vector<PP>,greater<PP> > q;
  q.push( PP(0,P(0,S)) );
  while(!q.empty()){
    PP p = q.top(); q.pop();
    int v=p.second.second;
    int m=p.second.first;
    if(minc[v][m]!=-1) continue;
    minc[v][m]=p.first;
    for(int i=0;i<G[v].size();i++){
      edge e=G[v][i];
      if(minc[e.to][m]==-1){
	q.push( PP(e.cost+p.first,P(m,e.to)) );
      }
      if(minc[e.to][m+1]==-1 && m<C){
	q.push( PP(e.cost/2+p.first,P(m+1,e.to)) );
      }
    }
  }
}

int main(){
  while(1){
    scanf("%d %d %d %d %d",&C,&N,&M,&S,&D);
    if(C==0 && N==0 && M==0 && S==0 && D==0) break;
    for(int i=0;i<M;i++){
      int a,b,f;
      scanf("%d %d %d",&a,&b,&f);
      edge e;
      e.to=b;e.cost=f;
      G[a].push_back(e);
      e.to=a;
      G[b].push_back(e);
    }
    solve();
    int res=INF;
    for(int i=0;i<=C;i++){
      if(minc[D][i]==-1) continue;
      res=min(res,minc[D][i]);
    }
    printf("%d\n",res);
    for(int i=1;i<=N;i++)
      G[i].clear();
  }
}