#CW7. 最长旅程(journey)

最长旅程(journey)

题目描述

有一张包含 nn 个点和 mm 条有向边的图。每条边都有一个正整数标签。

从某个点出发,可以沿有向边不断前进。若依次经过的点为

x0,x1,…,xk,x_0, x_1, \ldots, x_k,

则称这是一段长度为 kk 的行程,也就是连续走过了 kk 条边。

保证这张图中不存在可以无限进行的行程,从任意点出发都只能走有限条边。

对于每个点,考虑从它出发能够达到的最大行程长度。如果存在多种同样长的方案,则比较它们经过的边标签序列,选择其中字典序最小的一种。

对于每个起点,请输出所选行程的长度,以及该行程中所有边的标签之和。

这里,两个等长序列的字典序比较方式为:找到它们第一个不同的位置,当前位置数值更小的序列更小。

输入格式

第一行包含两个整数 n,mn, m。

接下来 mm 行,每行包含三个整数 ai,bi,pia_i, b_i, p_i,表示存在一条从城市 aia_i 指向城市 bib_i 的有向边,其标签为 pip_i,其中 1≤pi≤1091 \le p_i \le 10^9。

保证任意两个城市之间至多存在一条有向边,并且图中不存在无限长的行程。

输出格式

输出 nn 行。

第 ii 行输出两个整数,分别表示从城市 ii 出发所选择行程的:

  • 长度;
  • 所有边标签的总和。

样例 1 输入

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

样例 1 输出

0 0
1 10
1 10
2 20

样例 2 输入

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

样例 2 输出

0 0
1 10
1 5
2 7

数据范围

对于所有测试数据,保证:1≤n≤2⋅1051 \le n \le 2 \cdot 10^5,1≤m≤4⋅1051 \le m \le 4 \cdot 10^5,1≤ai,bi≤n1 \le a_i, b_i \le n,1≤pi≤1091 \le p_i \le 10^9。

测试点 n≤n \le m≤m \le 特殊性质
1∼41 \sim 4 1010 2020 无
5∼65 \sim 6 100100 200200
7∼107 \sim 10 10001000 50005000
11∼1211 \sim 12 2⋅1052 \cdot 10^5 4⋅1054 \cdot 10^5 所有 pip_i 全部相等
13∼1413 \sim 14 所有 pip_i 全部互不相同
15∼2015 \sim 20 无