#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX 10000000
#define n_MAX 101
#define c_MAX 11

int main() {

  while( true ) {

    long long int c, n, m, s, d;
    cin >> c >> n >> m >> s >> d;
    if ( n == 0 ) break;

    long long int l[n_MAX][n_MAX] = {0};

    for ( long long int i = 0; i < m; i++ ) {

      long long int a, b, f;
      cin >> a >> b >> f;
      l[a][b] = f;
      l[b][a] = f;

    }

    long long int t[c_MAX][n_MAX];
    for ( long long int j = 0; j <= c; j++ ) {
      for ( long long int i = 1; i <= n; i++ ) {
	t[j][i] = MAX;
      }
    }
    t[c][s] = 0;

    for ( long long int j = c; j >= 0; j-- ) {

      priority_queue< pair< int, int >, vector< pair< int, int > >, greater< pair< int, int > > > q;

      for ( long long int i = 1; i <= n; i++ ) {
	if ( t[j][i] < MAX ) {
	  q.push( make_pair( t[j][i], i ) );
	}
      }

      while( q.size() > 0 ) {

	pair< int, int > p;
	p = q.top();
	q.pop();
	long long int next = p.second;
	if ( t[j][next] < p.first ) continue;

	for ( long long int i = 1; i <= n; i++ ) {

	  if ( l[next][i] == 0 ) continue;
	  if ( t[j][i] > t[j][next] + l[next][i] ) {
	    t[j][i] = t[j][next] + l[next][i];
	    q.push( make_pair( t[j][i], i ) );
	  }
	  if ( j > 0 ) {
	    t[j - 1][i] = min( t[j - 1][i], t[j][next] + l[next][i] / 2 );
	  }

	}

      }

    }

    long long int ans = MAX;

    for ( long long int i = 0; i <= c; i++ ) {
      ans = min( ans, t[i][d] );
    }

    cout << ans << endl;

  }

  return 0;

}