好集合查询

题目描述

给定 $Q$ 个整数三元组 $(a_1, b_1, d_1), (a_2, b_2, d_2), \ldots, (a_Q, b_Q, d_Q)$。

集合 $\{1, 2, \ldots, Q\}$ 的子集 $S$ 被称为「好集合」，当存在一个长度为 $N$ 的整数序列 $(X_1, X_2, \ldots, X_N)$ 满足：

对所有的 $i \in S$，有 $X_{a_i} - X_{b_i} = d_i$。

初始时 $S$ 为空集，按 $i = 1, 2, \ldots, Q$ 的顺序执行以下操作：

如果 $S \cup \{i\}$ 是好集合，则将 $S$ 替换为 $S \cup \{i\}$。

按升序输出最终集合 $S$ 的所有元素。

输入格式

输入按以下格式从标准输入给出：

$N$ $Q$
$a_1$ $b_1$ $d_1$
$a_2$ $b_2$ $d_2$
$\vdots$
$a_Q$ $b_Q$ $d_Q$

输出格式

按以下格式输出最终集合 $S$ 的所有元素组成的序列 $(s_1, s_2, \ldots, s_k)$，各元素用空格隔开：

$s_1$ $s_2$ $\ldots$ $s_k$

样例

3 5
1 2 2
3 2 -3
2 1 -1
3 3 0
1 3 5

1 2 4 5

初始时 $S$ 为空集，按 $i = 1, 2, 3, 4, 5$ 的顺序执行题目中描述的操作，过程如下。

对于 $i = 1$，集合 $S \cup \{i\} = \{1\}$ 是好集合，因为例如 $(X_1, X_2, X_3) = (3, 1, 4)$ 满足题目条件，所以将 $S$ 替换为 $\{1\}$。

对于 $i = 2$，集合 $S \cup \{i\} = \{1, 2\}$ 是好集合，因为例如 $(X_1, X_2, X_3) = (3, 1, -2)$ 满足题目条件，所以将 $S$ 替换为 $\{1, 2\}$。

对于 $i = 3$，集合 $S \cup \{i\} = \{1, 2, 3\}$ 不是好集合。

对于 $i = 4$，集合 $S \cup \{i\} = \{1, 2, 4\}$ 是好集合，因为例如 $(X_1, X_2, X_3) = (3, 1, -2)$ 满足题目条件，所以将 $S$ 替换为 $\{1, 2, 4\}$。

对于 $i = 5$，集合 $S \cup \{i\} = \{1, 2, 4, 5\}$ 是好集合，因为例如 $(X_1, X_2, X_3) = (3, 1, -2)$ 满足题目条件，所以将 $S$ 替换为 $\{1, 2, 4, 5\}$。

因此，最终的集合 $S$ 为 $\{1, 2, 4, 5\}$。

200000 1
1 1 1

最终集合 $S$ 为空集。

5 20
4 2 125421359
2 5 -191096267
3 4 -42422908
3 5 -180492387
3 3 174861038
2 3 -82998451
3 4 -134761089
3 1 -57159320
5 2 191096267
2 4 -120557647
4 2 125421359
2 3 142216401
4 5 -96172984
3 5 -108097816
1 5 -50938496
1 2 140157771
5 4 65674908
4 3 35196193
4 4 0
3 4 188711840

1 2 3 6 8 9 11 14 15 16 17 19

数据范围

• 输入均为整数。
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le a_i, b_i \le N$
• $-10^9 \le d_i \le 10^9$