AT_abc352_f [ABC352F] Estimate Order

[problemUrl]: https://atcoder.jp/contests/abc352/tasks/abc352_f $ N $ 人の人がおり、人にはそれぞれ $ 1,\ 2,\ \ldots,\ N $ の番号が付けられています。 $ N $ 人が競争を行い、順位が付きました。この順位に対して以下の情報が与えられています。 - それぞれの人に対して付けられた順位は相異なる - 各 $ 1\ \leq\ i\ \leq\ M $ について人 $ A_i $ の順位を $ x $、人 $ B_i $ の順位を $ y $ とすると、$ x\ -\ y\ =\ C_i $ である ただし、この問題では与えられた情報に矛盾しないような順位付けが $ 1 $ つ以上存在するような入力のみが与えられます。 $ N $ 個のクエリの答えを求めてください。$ i $ 番目のクエリの答えは以下により定まる整数です。 - 人 $ i $ の順位が一意に定まるならば、その値を答えとする。そうでない場合、答えは $ -1 $ である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $

$ 1,\ 2,\ \ldots\ ,N $ 番目のクエリに対する答えをこの順に空白区切りで出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 16 $ - $ 0\ \leq\ M\ \leq\ \frac{N(N\ -\ 1)}{2} $ - $ 1\ \leq\ A_i,\ B_i\ \leq\ N $ - $ 1\ \leq\ C_i\ \leq\ N\ -\ 1 $ - $ (A_i,\ B_i)\ \neq\ (A_j,\ B_j)\ (i\ \neq\ j) $ - 与えられた情報に矛盾しない順位付けが $ 1 $ つ以上存在する - 入力される値はすべて整数 ### Sample Explanation 1 人 $ i $ の順位を $ X_i $ とおくと、$ (X_1,\ X_2,\ X_3,\ X_4,\ X_5) $ は $ (3,\ 4,\ 1,\ 2,\ 5),\ (3,\ 5,\ 2,\ 1,\ 4) $ のいずれかです。 したがって、$ 1 $ 番目のクエリに対する答えは $ 3 $、$ 2,\ 3,\ 4,\ 5 $ 番目のクエリに対する答えは $ -1 $ となります。