AT_abc328_f [ABC328F] Good Set Query

[problemUrl]: https://atcoder.jp/contests/abc328/tasks/abc328_f $ Q $ 個の整数の $ 3 $ つ組 $ (a_1,\ b_1,\ d_1),\ (a_2,\ b_2,\ d_2),\ \ldots,\ (a_Q,\ b_Q,\ d_Q) $ が与えられます。 集合 $ \lbrace\ 1,\ 2,\ \ldots,\ Q\rbrace $ の部分集合 $ 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\ \lbrace\ i\ \rbrace $ が良い集合なら、$ S $ を $ S\ \cup\ \lbrace\ i\ \rbrace $ で置き換える。 最終的な $ 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 $

### 制約 - 入力される値はすべて整数 - $ 1\ \leq\ N,\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ N $ - $ -10^9\ \leq\ d_i\ \leq\ 10^9 $ ### Sample Explanation 1 $ S $ が空集合である状態から始め、$ i\ =\ 1,\ 2,\ 3,\ 4,\ 5 $ の順に問題文中の操作を下記の通り行います。 - $ i\ =\ 1 $ について、集合 $ S\ \cup\ \lbrace\ i\ \rbrace\ =\ \lbrace\ 1\ \rbrace $ は良い集合です。なぜなら、例えば $ (X_1,\ X_2,\ X_3)\ =\ (3,\ 1,\ 4) $ が問題文中の条件を満たすからです。よって、$ S $ を $ \lbrace\ 1\rbrace $ で置き換えます。 - $ i\ =\ 2 $ について、集合 $ S\ \cup\ \lbrace\ i\ \rbrace\ =\ \lbrace\ 1,\ 2\ \rbrace $ は良い集合です。なぜなら、例えば $ (X_1,\ X_2,\ X_3)\ =\ (3,\ 1,\ -2) $ が問題文中の条件を満たすからです。よって、$ S $ を $ \lbrace\ 1,\ 2\rbrace $ で置き換えます。 - $ i\ =\ 3 $ について、集合 $ S\ \cup\ \lbrace\ i\ \rbrace\ =\ \lbrace\ 1,\ 2,\ 3\ \rbrace $ は良い集合ではありません。 - $ i\ =\ 4 $ について、集合 $ S\ \cup\ \lbrace\ i\ \rbrace\ =\ \lbrace\ 1,\ 2,\ 4\ \rbrace $ は良い集合です。なぜなら、例えば $ (X_1,\ X_2,\ X_3)\ =\ (3,\ 1,\ -2) $ が問題文中の条件を満たすからです。よって、$ S $ を $ \lbrace\ 1,\ 2,\ 4\rbrace $ で置き換えます。 - $ i\ =\ 5 $ について、集合 $ S\ \cup\ \lbrace\ i\ \rbrace\ =\ \lbrace\ 1,\ 2,\ 4,\ 5\ \rbrace $ は良い集合です。なぜなら、例えば $ (X_1,\ X_2,\ X_3)\ =\ (3,\ 1,\ -2) $ が問題文中の条件を満たすからです。よって、$ S $ を $ \lbrace\ 1,\ 2,\ 4,\ 5\rbrace $ で置き換えます。 よって、最終的な $ S $ は $ \lbrace\ 1,\ 2,\ 4,\ 5\rbrace $ です。 ### Sample Explanation 2 最終的な $ S $ は空集合です。