#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

int memo[11][100];

int main(){
  int c,n,m,s,d;
  while(scanf("%d%d%d%d%d",&c,&n,&m,&s,&d),c+n+m+s+d){
    int load[100][100] = {{ 0 }};
    priority_queue<pair<int,pair<int,int> > > pq;
    memset(memo, -1, sizeof(memo));
    s--; d--;
    REP(i,m){
      int a,b,f;
      scanf("%d%d%d",&a,&b,&f);
      load[a-1][b-1] = load[b-1][a-1] = f;
    }
    pq.push(mp(0,mp(c,s)));
    while(pq.size()){
      int pos  = pq.top().s.s;
      int dist = -pq.top().f;
      int chk  = pq.top().s.f;
      pq.pop();

      //printf("pq.size=%d, pos=%d, dist=%d, chk=%d\n",pq.size(),pos,dist,chk);
      if(pos == d){
        printf("%d\n",dist);
        break;
      }

      if(memo[chk][pos] != -1)
        continue;

      memo[chk][pos] = dist;

      REP(i,n){
        if(load[pos][i] != 0){
          int cost1 = dist + load[pos][i];
          int cost2 = dist + load[pos][i]/2;
          if(memo[chk][i] == -1)
            pq.push(mp(-cost1,mp(chk,i)));
          if(chk > 0 && memo[chk-1][i] == -1)
            pq.push(mp(-cost2,mp(chk-1,i)));
        }
      }
    }
  }
  return 0;
}