题目描述

Sirina 在一家名为“困难安装”的公司工作。公司在 $n$ 个城市设有分部，城市之间由 $m$ 条单向道路连接。

第 $i$ 条道路从城市 $a_i$ 通向城市 $b_i$，并有一个正整数吸引力 $t_i$。

保证：

• 任意两条道路不会连接同一对城市；
• 图中不存在无限行走路径。等价地说，整个有向图是 DAG。

Sirina 可以选择任意城市作为起点，然后沿任意一条有向路径行驶，并在路径终点进行安装。

对于一条路径，按行驶顺序记沿途道路的吸引力序列为 $(a_1,a_2,\ldots,a_k)$。

对每个起点城市，Sirina 按以下规则选择路径：

1. 首先使路径长度（经过的道路数）最大；
2. 如果最长路径不止一条，则选择吸引力序列字典序最小的那一条。

你的任务是对每个起点城市求出：

• 最终被选路径的长度；
• 该路径上所有道路吸引力之和。

输入格式

第一行包含两个整数 $n,m$：

• $1\le n\le2\cdot10^5$；
• $1\le m\le4\cdot10^5$。

接下来 $m$ 行，每行包含三个整数 $a_i,b_i,t_i$：

• $1\le a_i\ne b_i\le n$；
• $1\le t_i\le10^9$。

表示一条从 $a_i$ 指向 $b_i$、吸引力为 $t_i$ 的道路。

保证整个图不存在有向环。

输出格式

输出 $n$ 行。

第 $i$ 行输出两个以空格分隔的整数：

• 从城市 $i$ 出发按规则选择的路径长度；
• 该路径的吸引力总和。

样例

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

样例说明

• 城市 $1$ 没有出边，因此答案为 $(0,0)$；
• 从城市 $2$ 出发只能走 $2\to1$，答案为 $(1,10)$；
• 从城市 $3$ 出发只能走 $3\to1$，答案为 $(1,5)$；
• 从城市 $4$ 出发存在两条长度为 $2$ 的路径，其吸引力序列分别为 $(2,10)$ 与 $(4,5)$。前者字典序更小，因此答案为 $(2,12)$。

子任务