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

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 1 << 30
#define EPS 1e-10

typedef pair<int, int> pi; // 残りの割引券 現在の街
typedef pair<int, pi>P; // コスト pi
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

struct edge{ int to, cost; };

int C, V, E, S, D;
int d[128][16];
 vector<vector<edge> >G(128);
// int G[128];

void dijkstra(int s){
  priority_queue<P, vector<P>, greater<P> >q;
  rep(i, V) rep(j, C+1) d[i][j] = INF;
  d[s][C] = 0;
  q.push(MP(0, MP(C, s)));

  while(!q.empty()){
    P p = q.top(); q.pop();
    int v = p.S.S;
    int c = p.S.F;

    rep(i, G[v].size()){
      edge e = G[v][i];
      if(d[e.to][c] > d[v][c] + e.cost){
	d[e.to][c] = d[v][c] + e.cost;
	q.push(MP(d[e.to][c], MP(c, e.to)));
      }

      if( c > 0 && d[e.to][c-1] > d[v][c] + e.cost/2){
	  d[e.to][c-1] = d[v][c] + e.cost/2;
	  q.push(MP(d[e.to][c-1], MP(c-1, e.to)));
      }
    }
  }
}

int main(){
  while(scanf("%d%d%d%d%d", &C, &V, &E, &S, &D) && C+V+E+S+D){
    S--; D--;
    rep(i, 128){
      //      rep(j, 128) G[i][j] = INF;
      G[i].clear();
    }
    rep(i, E){
      int a, b, c;
      scanf("%d%d%d", &a, &b, &c); a--; b--;
     edge e;
      e.to = a; e.cost = c;
      G[b].PB(e);
      e.to = b;
      G[a].PB(e);
      //      G[a][b] = G[b][a] = c;
    }

    dijkstra(S);

    int res = INF;
    rep(i, C+1) res = min(res, d[D][i]);
    printf("%d\n", res);
    //    printf("%d\n", d[D][0]);
  }

  return 0;
}