#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
#define NONE -1

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

vector <int>	routes;
vector <int>	halfs;
int	kotae;
int	goal;
int coupon;

// ÅZoHTõ - Ö
void search_routes( int now )
{
	if ( kotae != NONE )
	{
		int half = accumulate( halfs.begin(), halfs.end(), 0 );
		if ( half >= kotae )
			return;
	}

	routes.push_back( now );
	if ( now == goal )
	{
		vector <int> r;
		for ( vector <int>::iterator it = routes.begin(); it != routes.end()-1; it++ )
		{
			r.push_back( edges[*(it+1)][*it] );
		}
		sort( r.rbegin(), r.rend() );
		for ( int i = 0; i < min( coupon, (int)r.size() ); i++ )
		{
			r[i] /= 2;
		}
		int sum = accumulate( r.begin(), r.end(), 0 );
		if ( kotae == NONE )
			kotae = sum;
		else
			kotae = min( sum, kotae );
	}
	else
	{
		for ( vector <int>::iterator it = adj[now].begin(); it != adj[now].end(); it++ )
		{
			if ( find( routes.begin(), routes.end(), *it ) == routes.end() )
			{
				halfs.push_back( edges[now][*it]/2 );
				search_routes( *it );
				halfs.pop_back();
			}
		}
	}
	routes.pop_back();
}

int main( void )
{
	// c: øÌ 1`10
	// n: oXªÂÈ®¬Ì 2`100
	// m: oXÌHü 1`500
	// s: start
	// d: goal
	int c, n, m, s, d;
	while ( cin >> c >> n >> m >> s >> d && c && n && m && s && d )
	{
		edges	=	vector < vector <int> >( 501, vector <int>(501, NONE) );
		adj		=	vector < vector <int> >( 501, vector <int>() );

		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;
			adj[a].push_back( b );
			adj[b].push_back( a );
		}

		routes	=	vector <int>(0);
		halfs	=	vector <int>(0);
		kotae	=	NONE;
		goal	=	d;
		coupon	=	c;

		search_routes( s );
		cout << kotae << endl;

	}

	return 0;
}