최소 최장 여행

베시는 코랜드에서 여행을 떠난다. 코랜드에는 $N$개($2\le N\le 2\cdot 10^5$)의 마을이 1번부터 $N$번까지 번호로 있고, $M$개($1\le M\le 4\cdot 10^5$)의 단방향 도로가 있다. $i$번째 도로는 마을 $a\_i$에서 마을 $b\_i$로 향하며, 라벨은 $l\_i$이다 ($1\le a\_i,b\_i\le N$, $1\le l\_i\le 10^9$).

마을 $x\_0$에서 시작하는 길이 $k$의 여행은 마을의 수열 $x\_0, x\_1, \ldots, x\_k$이며, 모든 $0\le i < k$에 대해 마을 $x\_i$에서 $x\_{i+1}$로 가는 도로가 있어야 한다. 코랜드에는 무한히 긴 여행이 없다고 보장된다. 또한 같은 두 마을을 잇는 도로는 두 개 이상 없다.

각 마을에서 시작하는 가장 긴 여행을 구하려고 한다. 출발점에 따라서는 가장 긴 여행이 여러 개일 수 있다. 이때 베시는 도로 라벨의 수열이 사전순으로 가장 작은 여행을 고른다. 길이가 같은 두 수열에서 처음으로 다른 위치의 원소가 더 작은 쪽이 사전순으로 작다.

각 마을에서 시작해 베시가 고르는 여행의 길이와 그 여행 도로 라벨의 합을 출력한다.

첫 줄에 $N$과 $M$이 주어진다.

이어서 $M$개의 줄에 세 정수 $a\_i$, $b\_i$, $l\_i$가 주어진다. 이는 마을 $a\_i$에서 마을 $b\_i$로 가는 라벨 $l\_i$의 도로를 뜻한다.

$N$개의 줄을 출력한다. $i$번째 줄에는 마을 $i$에서 시작해 베시가 고르는 여행의 길이와 도로 라벨의 합을 공백으로 구분해 출력한다.