题目描述

Bessie 正在奶牛大陆上旅行。奶牛大陆由从 $1$ 到 $N$ 编号的 $N$（$2 \le N \le 2\cdot 10^5$）座城市和 $M$（$1 \le M \le 4\cdot 10^5$）条单向道路组成。第 $i$ 条路从城市 $a_i$ 通向城市 $b_i$，标签为 $l_i$。

由城市 $x_0$ 开始的长度为 $k$ 的旅程被定义为一个城市序列 $x_0,x_1,\ldots,x_k$，对于所有的 $0 \le i < k$，存在由城市 $x_i$ 到 $x_{i+1}$ 的路。保证在奶牛大路上不存在长度无限的旅程，不存在两条路连接一对相同的城市。

对于每座城市，Bessie 想知道从它开始的最长旅程。对于一些城市，从它们开始的最长旅程不唯一，Bessie 将选择其中道路标签序列字典序更小的旅程。一个序列比等长的另一个序列字典序更小，当且仅当在它们不同的第一个位置，前者比后者的元素更小。

输出 Bessie 在每座城市选择的旅途的长度和道路标签之和。

输入格式

第一行包含 $N$ 和 $M$。

接下来 $M$ 行，每行三个整数 $a_i,b_i,l_i$，代表一条由 $a_i$ 到 $b_i$，标签为 $l_i$ 的单向道路。

输出格式

输出 $N$ 行，第 $i$ 行包含由空格分隔的两个整数，表示 Bessie 选择的从城市 $i$ 开始的旅程的长度和道路标签之和。

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

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

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

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

提示

样例解释 2

在下面的解释中，我们用 $a_i\xrightarrow{l_i} b_i$ 表示由城市 $a_i$ 通往 $b_i$，标签为 $l_i$ 的单向道路。

从城市 $4$ 出发有多条旅程，包含 $4\xrightarrow{4} 3\xrightarrow 5 1$，$4\xrightarrow 1 1$ 和 $4\xrightarrow 2 2\xrightarrow{10} 1$。在这些旅程中，$4\xrightarrow{4} 3\xrightarrow 5 1$ 和 $4\xrightarrow 2 2\xrightarrow{10} 1$ 是最长的。它们的长度均为 $2$，道路标签序列分别为 $[4,5]$ 和 $[2,10]$。$[2,10]$ 是字典序更小的那一个，它的和为 $12$。

测试点性质

• 测试点 $5-6$ 满足所有道路的标签相同。
• 测试点 $7-8$ 满足所有道路的标签不相同。
• 测试点 $9-10$ 满足 $N,M \le 5000$。
• 测试点 $11-20$ 没有额外限制。