Page not loading? Try clicking here.
Placeholder

#6097
Subtask

최장 여행 일정 2s 1024MB

Problems

Bessie is going on a trip in Cowland, which has N (2≤N≤2⋅10^5) towns numbered from 1 to N and M (1≤M≤4⋅10^5) one-way roads. The i-th road runs from town a_i to town b_i and has label l_i (1≤a_i,b_i≤N, 1≤l_i≤10^9).

A trip of length k starting at town x_0 is a sequence of towns x_0,x_1,…,x_k, such that there is a road from town x_i to town x_{i+1} for all 0≤i<k. It is guaranteed that there are no trips of infinite length in Cowland, and that no two roads connect the same pair of towns.

For each town, Bessie wants to know the longest possible trip starting at it. For some starting owns, there are multiple longest trips - out of these, she prefers the trip with the lexicographically minimum sequence of road labels. A sequence is lexicographically smaller than another sequence of the same length if, at the first position in which they differ, the first sequence has a smaller element than the second sequence.

Output the length and sum of road labels of Bessie's preferred trip starting at each town.


Input

The first line contains N and M.

The next M lines each contain three integers a_i, b_i, and l_i, denoting a road from ai to bi with label l_i.


Output

Output N lines. The ith should contain two space-separated integers, the length and sum of road labels of Bessie's preferred trip starting at town i.


Subtask

# Score Condition
#110

All labels are the same.

#220

All labels are distinct.

#330

N,M≤5000

#440

No additional constraints.


Example #1

4 5
4 3 10
4 2 10
3 1 10
2 1 10
4 1 10
0 0
1 10
1 10
2 20

Example #2

4 5
4 3 4
4 2 2
3 1 5
2 1 10
4 1 1
0 0
1 10
1 5
2 12

In the following explanation, we let a_i\overset{l_i}\to b_i represent the road from a_i to b_i with label l_i.

There are several trips starting from vertex 4, including 4 \overset{4}\to 3\overset{5}\to 1, 4\overset{1}\to 1, and 4\overset{2}\to 2\overset{10}\to 1. Of these trips, 4 \overset{4}\to 3\overset{5}\to 1 and 4\overset{2}\to 2\overset{10}\to 1 are the longest. These trips each have length 2, and their road label sequences are [4,5] and [2,10], respectively.

[2,10] is the lexicographically smaller sequence, and its sum is 12.


Example #3

4 5
4 3 2
4 2 2
3 1 5
2 1 10
4 1 1
0 0
1 10
1 5
2 7

Example #4

4 5
4 3 2
4 2 2
3 1 10
2 1 5
4 1 1
0 0
1 5
1 10
2 7


Source

USACO 2023 December Gold

You must sign in to write code.