#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

/* 現在地 コスト 使った枚数 */
typedef tuple<int,int,int> tp;
typedef pair<ll,ll> P;

/* 町 使った割引券の数 */
ll dist[105][15];
vector<P> G[105];
const ll MAX=LLONG_MAX/10;

void init(){
  for(int i=0;i<105;i++){
    G[i].clear();
    for(int j=0;j<15;j++){
      dist[i][j]=MAX;
    }
  }
}

void solve(int c,int n,int m,int s,int d){
  init();
  int a,b,f;
  for(int i=0;i<m;i++){
    cin>>a>>b>>f;
    G[a].push_back(mp(b,f));
    G[b].push_back(mp(a,f));
  }

  /* 現在地 使った枚数 */
  priority_queue<tp,vector<tp>,greater<tp> > que;
  que.push(make_tuple(s,0,0));
  dist[s][0] = 0;
  while(que.size()){
    ll now,cost,num;
    tie(now,cost,num)=que.top();que.pop();
    if(dist[now][num]<cost)continue;
    for(auto x : G[now]){      
      /* 割引券を使わない */
      if(cost+x.second<dist[x.first][num]){
        dist[x.first][num] = cost+x.second;
        que.push(make_tuple(x.first,dist[x.first][num],num));
      }
      /* 割引券が残っていたら使う */
      if(num<c&&cost+x.second/2<dist[x.first][num+1]){
          dist[x.first][num+1] = cost+x.second/2;
          // cout<<now<<" "<<x.first<<" = "<< dist[x.first][num+1] << endl;
          que.push(make_tuple(x.first,dist[x.first][num+1],num+1));
        }
    }
  }

  ll ans=LLONG_MAX;
  for(int i=0;i<15;i++)
      ans=min(ans,dist[d][i]);
  ans=min(ans,dist[d][c]);
  
  cout<<ans<<endl;
}


int main(){
  int c,n,m,s,d;
  while(cin>>c>>n>>m>>s>>d,c|n|m|s|d){
    solve(c,n,m,s,d);
  }
}
	 

