#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;
struct Edge{ int to, cost; };
vector<Edge> G[101];
int dist[11][101];
const int INF = (1<<28);
int dijkstra( int s, int a ){
  priority_queue< P, vector<P>, greater<P> > q;
  for( int j=0; j<=100; j++ )
    dist[a][j] = INF;
  dist[a][s] = 0;
  q.push({ 0, s });
  while( !q.empty() ){
    int cost = q.top().first;
    int v = q.top().second;
    q.pop();
    if( dist[a][v] < cost ) continue;
    for( auto it=G[v].begin(); it!=G[v].end(); ++it ){
      int d = dist[a][v] + it->cost;
      if( a > 0 )
        d = min( d, dist[a-1][v] + it->cost/2 );
      if( dist[a][it->to] > d ){
        dist[a][it->to] = d;
        q.push({ d, it->to });
      }
    }
  }
  //for( int i=1; i<=3; i++ )
  //  cout << dist[a][i] << ' '; cout << endl;
}
int main( void ){
  while( 1 ){
    int c,n,m,s,d,a,b,f;
    cin >> c >> n >> m >> s >> d;
    if( c == 0 ) break;
    for( int i=1; i<=n; i++ ) G[i].clear();
    for( int i=0; i<m; i++ ){
      cin >> a >> b >> f;
      G[a].push_back({ b, f });
      G[b].push_back({ a, f });
    }
    for( int i=0; i<=c; i++ )
      dijkstra( s, i );
    cout << dist[c][d] << endl;
  }
}