#include <stdio.h>
#include <stdlib.h>

using namespace std;

class pdata  {
	public:
		int* city_1;
		int* city_2;
		int* dist_b;
		int st_city;
		int en_city;
		int t_cities;
		int t_roads;
		int min_dist;
		bool first_time;
} pd;

int find_minimum_distance( int given_city , int cur_dist , int table[] , int num_of_cities_in_table );

int main( void )  {
	int i;
	FILE* apo_in;
	FILE* apo_out;
	pd.min_dist = 0;
	pd.first_time = true;
	apo_in = fopen( "apollon.in" , "r" );
	fscanf( apo_in , "%i" , &pd.t_cities );
	fseek( apo_in , 1 , SEEK_CUR );
	fscanf( apo_in , "%i\n" , &pd.t_roads );
	pd.city_1 = ( int* )malloc( pd.t_roads * sizeof( int ) );
	pd.city_2 = ( int* )malloc( pd.t_roads * sizeof( int ) );
	pd.dist_b = ( int* )malloc( pd.t_roads * sizeof( int ) );
	for( i = 1 ; i < pd.t_roads + 1 ; i++ )  {
		fscanf( apo_in , "%i" , &pd.city_1[ i ] );
		fseek( apo_in , 1 , SEEK_CUR );
		fscanf( apo_in , "%i" , &pd.city_2[ i ] );
		fseek( apo_in , 1 , SEEK_CUR );
		fscanf( apo_in , "%i\n" , &pd.dist_b[ i ] );
	}
	fscanf( apo_in , "%i" , &pd.st_city );
	fseek( apo_in , 1 , SEEK_CUR );
	fscanf( apo_in , "%i\n" , &pd.en_city );
	fclose( apo_in );

	int* table;
	table = ( int* )malloc( ( pd.t_cities ) * sizeof( int ) );
	find_minimum_distance( pd.st_city , 0 , table , 0 );

	apo_out = fopen( "apollon.out" , "w" );
	fprintf( apo_out , "%i\n" , pd.min_dist );
	fclose( apo_out );
	return( 0 );
}

int find_minimum_distance( int given_city , int cur_dist , int table[] , int num_of_cities_in_table )  {
	bool passed_city = false;
	int i;
	int j;

	if( given_city == pd.en_city )  {
		if( cur_dist < pd.min_dist || pd.first_time == true )  {
			pd.min_dist = cur_dist;
			pd.first_time = false;
		}
	}
	else  {
		num_of_cities_in_table++;
		table[ num_of_cities_in_table ] = given_city;

		for( i = 1 ; i < pd.t_roads + 1 ; i++ )  {
			if( pd.city_1[ i ] == given_city )  {
				passed_city = false;
				j = 1;
				while( j < num_of_cities_in_table + 1 && passed_city == false ) {
					if( table[ j ] == pd.city_2[ i ] )
						passed_city = true;
					else
						j++;
				}
				if( passed_city == false )  {
						cur_dist = cur_dist + pd.dist_b[ i ];
						if( cur_dist < pd.min_dist || pd.first_time == true )
							find_minimum_distance( pd.city_2[ i ] , cur_dist , table , num_of_cities_in_table );
						cur_dist = cur_dist - pd.dist_b[ i ];
				}
			}
			passed_city = false;
			if( pd.city_2[ i ] == given_city )  {
				passed_city = false;
				j = 1;
				while( j < num_of_cities_in_table + 1 && passed_city == false ) {
					if( table[ j ] == pd.city_1[ i ] )
						passed_city = true;
					else
						j++;
				}
				if( passed_city == false )  {
						cur_dist = cur_dist + pd.dist_b[ i ];
						if( cur_dist < pd.min_dist || pd.first_time == true )
							find_minimum_distance( pd.city_1[ i ] , cur_dist , table , num_of_cities_in_table );
						cur_dist = cur_dist - pd.dist_b[ i ];
				}
			}
		}
	}
	return( 0 );
};