P9981 [USACO23DEC] Minimum Longest Trip G

Bessie is traveling on Cowland. Cowland consists of $N$ cities numbered from $1$ to $N$ ($2 \le N \le 2\cdot 10^5$) and $M$ one-way roads ($1 \le M \le 4\cdot 10^5$). The $i$-th road goes from city $a_i$ to city $b_i$ and has label $l_i$ ($1 \le l_i \le 10^9$). A trip 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 is no trip of infinite length in Cowland, and there are no two roads connecting the same ordered pair of cities. For each city, Bessie wants to know the longest trip starting from it. For some cities, the longest trip starting from them is not unique, so Bessie will choose the one whose road-label sequence is lexicographically smaller. A sequence is lexicographically smaller than another sequence of the same length if and only if, at the first position where they differ, the element in the former sequence is smaller. Output the length of the trip Bessie chooses for each city and the sum of the road labels along that trip.

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 $N$ lines. The $i$-th line contains two integers separated by a space, representing the length of the trip Bessie chooses starting from city $i$ and the sum of the road labels along that trip.

### 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 city $b_i$ with label $l_i$. Starting from city $4$, there are multiple trips, including $4\xrightarrow{4} 3\xrightarrow 5 1$, $4\xrightarrow 1 1$, and $4\xrightarrow 2 2\xrightarrow{10} 1$. Among these trips, $4\xrightarrow{4} 3\xrightarrow 5 1$ and $4\xrightarrow 2 2\xrightarrow{10} 1$ are the longest. Their lengths are both $2$, and their road-label sequences are $[4,5]$ and $[2,10]$, respectively. $[2,10]$ is lexicographically smaller, and its sum is $12$. ### Test Point Properties - Test points $5-6$ satisfy that all road labels are the same. - Test points $7-8$ satisfy that all road labels are distinct. - Test points $9-10$ satisfy $N, M \le 5000$. - Test points $11-20$ have no additional constraints. Translated by ChatGPT 5