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

#define INF -1
#define NILL -1
#define TRUE 1
#define FALSE 0

int jeManji( int i, int j ) 
{
	if ( i == INF ) return FALSE;
	if ( j== INF) return TRUE;
	
	return i < j;
}

int nadjiMinimum( int *obidjen, int *d, int n ) 
{
	// TODO
}

void relax( int **graf, int *d, int *pret, int u, int v ) 
{
	// TODO
}

void dijkstra( int **graf, int *obidjen, int *d, int *pret, int n )
{
	// TODO
}

int rekonstrukcija( int i, int polaziste, int *pret, int *dS, int *dA ) 
{
	// TODO
}

int main() 
{
	int n, m;
	scanf("%d%d", &n, &m );

	int **graf = ( int ** ) malloc( n * sizeof( int * ) );
	int *dS = ( int * ) malloc( n * sizeof( int) );
	int *dA = ( int * ) malloc( n * sizeof( int ) );
	int *pretS = ( int * ) malloc( n * sizeof( int ) );
	int *pretA = ( int * ) malloc( n * sizeof( int ) );
	int *obidjenS = ( int * ) malloc( n * sizeof( int ) );
	int *obidjenA = ( int * ) malloc( n * sizeof( int ) );

	//INICIJALIZACIJA
	for ( int i = 0; i < n; i ++ ) 
	{
		graf[ i ] = ( int * ) malloc( n * sizeof( int ) );
		for ( int j = 0; j < n; j ++ ) graf[ i ][ j ] = INF;
		
		dS[ i ] = dA[ i ] = INF;
		pretS[i] = pretA[ i ] = NILL;
		obidjenS[ i ] = obidjenA[ i ] = FALSE;
	}
	
	//UCITAVANJE
	for ( int i = 0; i < m; i ++ ) 
	{
		int u, v, t;
		scanf("%d%d%d", &u, &v, &t );
		
		graf[ u ][ v ] = t;
		graf[ v ][ u ] = t;
	}

	int a, s, g;
	scanf("%d%d%d", &a, &s, &g);
	
	// TODO
		
	return 0;
}