Problem Description

Bessie is traveling on the Cow Continent, which consists of \( N \) ( \( 2 \le N \le 2 \cdot 10^5 \) ) cities numbered from 1 to \( N \) and \( M \) ( \( 1 \le M \le 4 \cdot 10^5 \) ) one-way roads. The \( i \)-th road goes from city \( a_i \) to city \( b_i \) with a label \( l_i \).

A journey of length \( k \) starting from city \( x_0 \) is defined as a sequence of cities \( x_0, x_1, \ldots, x_k \) such that for all \( 0 \le i < k \), there exists a road from city \( x_i \) to \( x_{i+1} \). It is guaranteed that there are no infinitely long journeys on the Cow Continent and no two roads connect the same pair of cities.

For each city, Bessie wants to know the length of the longest journey starting from it. For some cities, there may be multiple longest journeys, and Bessie will choose the one with the lexicographically smaller sequence of road labels. A sequence is lexicographically smaller than another of the same length if and only if at the first position where they differ, the former has a smaller element.

Output the length and the sum of road labels of the journey Bessie chooses for each city.

Input Format

The first line contains \( N \) and \( M \).

The next \( M \) lines each contain three integers \( a_i, b_i, l_i \), representing a one-way road from \( a_i \) to \( b_i \) with label \( l_i \).

Output Format

Output \( N \) lines, each containing two integers separated by a space, representing the length and the sum of road labels of the journey Bessie chooses starting from city \( i \).

Sample Input and Output

Input Sample #1

4 5
4 3 10
4 2 10
3 1 10
2 1 10
4 1 10

Output Sample #1

0 0
1 10
1 10
2 20

Input Sample #2

4 5
4 3 4
4 2 2
3 1 5
2 1 10
4 1 1

Output Sample #2

0 0
1 10
1 5
2 12

Input Sample #3

4 5
4 3 2
4 2 2
3 1 5
2 1 10
4 1 1

Output Sample #3

0 0
1 10
1 5
2 7

Input Sample #4

4 5
4 3 2
4 2 2
3 1 10
2 1 5
4 1 1

Output Sample #4

0 0
1 5
1 10
2 7

Notes

Sample Explanation 2

In the explanation below, we use \( a_i \xrightarrow{l_i} b_i \) to denote a one-way road from city \( a_i \) to \( b_i \) with label \( l_i \).

Starting from city 4, there are multiple journeys, including \( 4 \xrightarrow{4} 3 \xrightarrow{5} 1 \), \( 4 \xrightarrow{1} 1 \), and \( 4 \xrightarrow{2} 2 \xrightarrow{10} 1 \). Among these journeys, \( 4 \xrightarrow{4} 3 \xrightarrow{5} 1 \) and \( 4 \xrightarrow{2} 2 \xrightarrow{10} 1 \) are the longest. Both have a length of 2, with road label sequences \([4, 5]\) and \([2, 10]\) respectively. \([2, 10]\) is the lexicographically smaller one, and its sum is 12.

Test Case Properties

• Test cases \( 5-6 \) have all roads with the same label.
• Test cases \( 7-8 \) have all roads with different labels.
• Test cases \( 9-10 \) have \( N, M \le 5000 \).
• Test cases \( 11-20 \) have no additional restrictions.

见题面 Input 部分

见题面 Output 部分