{"raw_statement":[{"iden":"statement","content":"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$（$1 \\le l_i \\le 10^9$）。\n\n由城市 $x_0$ 开始的长度为 $k$ 的旅程被定义为一个城市序列 $x_0,x_1,\\ldots,x_k$，对于所有的 $0 \\le i < k$，存在由城市 $x_i$ 到 $x_{i+1}$ 的路。保证在奶牛大陆上不存在长度无限的旅程，不存在两条路连接一对相同的城市。\n\n对于每座城市，Bessie 想知道从它开始的最长旅程。对于一些城市，从它们开始的最长旅程不唯一，Bessie 将选择其中道路标签序列字典序更小的旅程。一个序列比等长的另一个序列字典序更小，当且仅当在它们不同的第一个位置，前者比后者的元素更小。\n\n输出 Bessie 在每座城市选择的旅途的长度和道路标签之和。"},{"iden":"input","content":"第一行包含 $N$ 和 $M$。\n\n接下来 $M$ 行，每行三个整数 $a_i,b_i,l_i$，代表一条由 $a_i$ 到 $b_i$，标签为 $l_i$ 的单向道路。"},{"iden":"output","content":"输出 $N$ 行，第 $i$ 行包含由空格分隔的两个整数，表示 Bessie 选择的从城市 $i$ 开始的旅程的长度和道路标签之和。"},{"iden":"note","content":"### 样例解释 2\n\n在下面的解释中，我们用 $a_i\\xrightarrow{l_i} b_i$ 表示由城市 $a_i$ 通往 $b_i$，标签为 $l_i$ 的单向道路。\n\n从城市 $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$。\n\n### 测试点性质\n\n- 测试点 $5-6$ 满足所有道路的标签相同。\n- 测试点 $7-8$ 满足所有道路的标签不相同。\n- 测试点 $9-10$ 满足 $N,M \\le 5000$。\n- 测试点 $11-20$ 没有额外限制。"}],"translated_statement":null,"sample_group":[["4 5\n4 3 10\n4 2 10\n3 1 10\n2 1 10\n4 1 10","0 0\n1 10\n1 10\n2 20"],["4 5\n4 3 4\n4 2 2\n3 1 5\n2 1 10\n4 1 1","0 0\n1 10\n1 5\n2 12"],["4 5\n4 3 2\n4 2 2\n3 1 5\n2 1 10\n4 1 1","0 0\n1 10\n1 5\n2 7"],["4 5\n4 3 2\n4 2 2\n3 1 10\n2 1 5\n4 1 1","0 0\n1 5\n1 10\n2 7"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}