#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

#define NONE -1

// c: øÌ 1`10
// n: oXªÂÈ®¬Ì 2`100
// m: oXÌHü 1`500
// s: start
// d: goal
int c, n, m, s, d;

// ÅZoHTõ - Ï
vector < vector <int> >	edges;

int search()
{
	// Å¬l
	vector < vector <int> >		D( n, vector <int>(c+1,NONE) );
	// KâÏÝÌm[h
	vector < vector <bool> >	V( n, vector <bool>(c+1,false) );

	D[s][c] = 0;

	while (1)
	{
		int u, w, minv = NONE;
		for ( int i = 0; i < n; i++ )
		{
			for ( int j = 0; j < c+1; j++ )
			{
				if ( V[i][j] == false && D[i][j] != NONE && ( minv == NONE || minv > D[i][j] ) )
				{
					minv = D[i][j];
					u = i;
					w = j;
				}
			}
		}
		if ( minv == NONE )
			break;

		V[u][w] = true;

		for ( int v = 0; v < n; v++ )
		{
			if ( edges[u][v] == NONE )
				continue;

			if ( D[v][w] == NONE )
				D[v][w] = D[u][w] + edges[u][v];
			else
				D[v][w] = min( D[v][w], D[u][w] + edges[u][v] );

			if ( w )
			{
				if ( D[v][w-1] == NONE )
					D[v][w-1] = D[u][w] + edges[u][v]/2;
				else
					D[v][w-1] = min(D[v][w-1], D[u][w] + edges[u][v]/2);
			}
		}

	}

	int minv = NONE;
	for ( int i = 0; i < c+1; i++ )
	{
		if ( D[d][i] != NONE )
		{
			if ( minv == NONE )
				minv = D[d][i];
			else
				minv = min( minv, D[d][i] );
		}
	}
	return minv;

}

int main( void )
{
	while ( cin >> c >> n >> m >> s >> d && c && n && m && s && d )
	{
		edges	=	vector < vector <int> >( 101, vector <int>(101, NONE) );
		s--;
		d--;


		// ú»
		for ( int i = 0; i < m; i++ )
		{
			// f: a-bÔÌRXg
			int a, b, f;
			cin >> a >> b >> f;

			a--;
			b--;

			edges[a][b] = f;
			edges[b][a] = f;

		}


		// Tõ
		int kotae = search();
		cout << kotae << endl;

	}

	return 0;
}