题目描述

给定 $m$ 组形如 $\min (x_{a_i},x_{b_i})=c_i$ 的关系式，请构造一个长度为 $n$ 的数组 $x$，使得数组中的每个数字在 $1$ 到 $10^9$ 之间，并且该数组满足所有的关系式。

题目保证数组存在。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个数字 $a_i,b_i,c_i$。

输出格式

共一行 $n$ 个整数，代表你构造的数组 $x$。

本题已启用 Special Judge，满足题目条件的任何答案都将视为正确。

2 1
2 1 7

9 7

5 6
1 2 1
3 5 4
1 5 3
1 3 3
2 3 1
2 4 1

3 1 4 1 5

2 5
1 2 1
2 1 1
1 2 1
1 2 1
2 1 1

1 1

5 1
1 2 123

123 1000000000 3 4 26311337

提示

样例 1 解释

显然，$\min (x_2,x_1) = \min (9,7) =7$，满足题目条件。

样例 3 解释

第一个限制为 $\min (x_1,x_2) =1$，所有的条件实际上和这个限制一样。

样例 4 解释

唯一的限制为 $\min (x_1,x_2) =123$，其余的数字可以是介于 $1$ 到 $10^9$ 之间的任何数字。

数据范围

对于 $100\%$ 的数据：$1 \leq n,m \leq 10^5$，$1 \leq a_i ,b_i \leq n$，$a_i \neq b_i$，$1 \leq c_i \leq 10^9$。

本地 Checker 使用说明

附件提供 Windows 本地校验器 checker.exe，用于检查自己程序生成的输出。

大样例只提供输入文件 .in，不提供标准答案 .ans。Checker 只需要输入文件和自己的输出文件，即可直接检查构造是否合法。

1. 准备文件

先运行自己的程序，读取给定的输入文件，并将输出保存到文件中。以下以输入文件 data.in、自己的输出文件 my.out 为例。

将 checker.exe、data.in 和 my.out 放在同一文件夹中，并在该文件夹打开终端。

2. 运行校验器

在 Windows PowerShell 或命令提示符中执行：

.\checker.exe "data.in" "my.out"

两个参数的顺序为：输入文件在前，自己的输出文件在后。请将示例中的文件名替换为实际文件名；也可以填写完整路径，路径含空格时需要保留双引号。

例如，若输入文件名为 大样例1.in，自己的输出文件名为 大样例1.out，则执行：

.\checker.exe "大样例1.in" "大样例1.out"

3. 查看结果

• 显示 AC：输出合法，满足该输入文件的全部要求。
• 显示 WA：输出不合法。校验器会给出错误原因；若某个关系式不满足，会指出关系式编号、对应下标、要求的值和实际值。
• 显示 ERROR：请根据提示检查输入文件或命令参数。

校验器会检查：

1. 输出是否恰好包含 $n$ 个整数；
2. 每个整数是否都在 $[1,10^9]$ 范围内，包括未出现在关系式中的位置；
3. 给定的每个关系式是否都成立；
4. 是否存在多余的数字、调试文字等内容。