/*
* Za uneti orijentisani graf, proveriti da li je aciklican.
* Ako jeste, izvrsiti topolosko sortiranje.
* Ako nije, stampati vezu koja je napravila ciklus.
*/

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

#define POVEZANO 1
#define NEPOVEZANO 0
#define NEDEFINISANO -1

int time = 0, br;

void dfs( int **graf, int n, int *d, int *f, int *pre, int c, int *topsort )
{
	d[ c ] = ++time;

	for ( int i = 0; i < n; i ++ )
	{
		if ( graf[ c ][ i ] == POVEZANO && pre[ c ] != i )
			if ( d[ i ] == NEDEFINISANO ) 
			{
				pre[ i ] = c;
				dfs( graf, n, d, f, pre, i, topsort );
			}
		   else if ( f[ i ] == NEDEFINISANO ) printf("Ima ciklus i grana (%d, %d) pripada tom ciklusu\n", c, i);
	}

	f[ c ] = ++ time;
	topsort[ --br ] = c;
}

int main() 
{
	int n, l;
	scanf("%d%d", &n, &l );
	
	int **graf = ( int ** ) malloc( n * sizeof( int * ) );
	for ( int i = 0; i < n; i ++ )
		graf[ i ] = ( int * ) malloc( n * sizeof( int ) );
	
	int *d = ( int * ) malloc( n * sizeof( int ) );
	int *f = ( int * ) malloc( n * sizeof( int ) );
	int *pre = ( int * ) malloc( n * sizeof( int ) );
	int *topsort = ( int * ) malloc( n * sizeof( int ) );
	
	for ( int i = 0; i < n; i ++ )
		for ( int j = 0; j < n; j ++ )
			graf[ i ][ j ] = NEPOVEZANO;
	
	for ( int i = 0; i < l; i ++ ) 
	{
		int u, v;
		scanf("%d%d", &u, &v );
		
		graf[ u ][ v ] = POVEZANO;
		//graf[v][u] = POVEZANO;
	}
	
	for ( int i = 0; i < n; i ++ ) 
		pre[ i ] = d[ i ] = f[ i ] = NEDEFINISANO;
	
	br = n;
	for ( int i = 0; i < n; i ++ )
		if ( d[ i ] == NEDEFINISANO ) dfs( graf, n, d, f, pre, i, topsort );

	for ( int i = 0; i < n; i ++ )
		printf("%d %d %d %d\n", i, d[ i ], f[ i ], pre[ i ] );

	for ( int i = 0; i < n; i ++ )
		printf("%d ", topsort[ i ] );
	putchar('\n');

	return 0;
}