Longest Journey on Cow Land

Bessie is traveling on Cow Land. Cow Land consists of \(N\) cities numbered from \(1\) to \(N\) and \(M\) directed roads. The \(i\)-th road goes from city \(a_i\) to city \(b_i\) with label \(l_i\). A journey of length \(k\) starting from city \(x_0\) is defined as a sequence \(x_0,x_1,\ldots,x_k\) such that for every \(0 \le i < k\), there exists a road from \(x_i\) to \(x_{i+1}\). It is guaranteed that there is no journey of infinite length and that no two roads connect the same pair of cities.

For each city, Bessie wants to know the longest journey starting from that city. If there are multiple journeys achieving the maximum length, she chooses the one whose sequence of road labels is lexicographically smallest. Two sequences of equal length are compared lexicographically: they are compared at the first position where they differ, and the sequence with the smaller value at that position is chosen.

Output for each city the length of the chosen journey and the sum of the road labels along that journey.

inputFormat

The first line contains two integers \(N\) and \(M\) \((2 \le N \le 2\cdot10^5, 1 \le M \le 4\cdot10^5)\), which represent the number of cities and the number of roads, respectively.

Each of the following \(M\) lines contains three integers: \(a_i\), \(b_i\), and \(l_i\). This means there is a directed road from city \(a_i\) to city \(b_i\) with label \(l_i\). It is guaranteed that no two roads connect the same pair of cities and that no journey is of infinite length.

outputFormat

Output \(N\) lines. The \(i\)-th line should contain two integers: the length of the chosen journey starting from city \(i\) and the sum of its road labels.

sample

3 3
1 2 5
2 3 7
1 3 10

2 12
1 7
0 0