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

void flojdWarshall(int **graf, int **pret, int n)
{
	for( int k = 0; k < n; k ++ )
		for( int i = 0; i < n; i ++ )
			for( int j = 0; j < n; j ++ )
				if( graf[ i ][ j ] > graf[ i ][ k ] + graf[ k ][ j ] )
				{
					graf[ i ][ j ] = graf[ i ][ k ] + graf[ k ][ j ];
					pret[ i ][ j ] = pret[ k ][ j ];
				}
}

void printMatrix(int **graf,int n)
{
	for( int i = 0; i < n; i ++ )
	{
		for( int j = 0; j < n; j ++ )
			printf("%d ",graf[ i ][ j ] );

		printf("\n");
	}
}

void rec( int **pret, int i, int j )
{
	while ( pret[ i ][ j ] != i )
	{
		printf("%d\n", pret[ i ][ j ] );
		j = pret[ i ][ j ];
	}
}

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

	int **graf=(int **)malloc(n*sizeof(int *));
	int **pret=(int **)malloc(n*sizeof(int *));

	//inicijalizacija grafa
	for( int i = 0; i < n; i ++ )
	{
		graf[ i ] = ( int * ) malloc( n * sizeof( int ) );
		pret[ i ] = ( int * ) malloc( n * sizeof( int ) );
		for( int j = 0; j < n; j ++ )
		{
			graf[ i ][ j ] = INT_MAX / 2;
			pret[ i ][ j ] = 0;
		}
		graf[ i ][ i ] = 0;		
	}

	//unosenje veza
	for( int i = 0; i < m; i ++ )
	{
		int x, y, tezina;
		scanf("%d%d%d", &x, &y, &tezina );
		graf[ x ][ y ] = graf[ y ][ x ] = tezina;
		pret[ x ][ y ] = x;
		pret[ y ][ x ] = y;
	}

	flojdWarshall( graf, pret, n );
	printMatrix( graf, n );
	printMatrix( pret, n );
	rec( pret, 0, 2 );
	return 0;
}