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

#define NONE -1

int c,n,m,s,d;
vector < vector <int> > P;
vector < vector <int> > E;
vector <int> R;
vector <bool> V;
int answer;

void solve( int t )
{
	if ( t == d )
	{
		sort( R.rbegin(), R.rend() );
		for ( int i = 0; i < min(c,(int)R.size()); i++ )
		{
			R[i] /= 2;
		}
		if ( answer == -1 )
			answer = accumulate( R.begin(), R.end(), 0 );
		else
			answer = min( answer, accumulate( R.begin(), R.end(), 0 ) );
	}
	else
	{
		V[t] = true;
		for ( vector <int>::iterator it = E[t].begin(); it != E[t].end(); it++ )
		{
			if ( V[*it] == false )
			{
				R.push_back( P[t][*it] );
				solve(*it);
				R.pop_back();
			}
		}
		V[t] = false;
	}
}

int main( void )
{
	while ( cin >> c >> n >> m >> s >> d && c && n && m && s && d )
	{
		s--;
		d--;
		P = vector < vector <int> >(n+1, vector <int>(n+1,NONE));
		E = vector < vector <int> >(n+1);
		for ( int i = 0; i < m; i++ )
		{
			int a, b, f;
			cin >> a >> b >> f;
			P[a-1][b-1] = f;
			P[b-1][a-1] = f;
			E[a-1].push_back( b-1 );
			E[b-1].push_back( a-1 );
		}

		R = vector <int>();
		V = vector <bool>(n+1,false);
		answer = -1;
		solve( s );
		cout << answer << endl;
	}

	return 0;
}