I - Estimate Order 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 525 点

問題文

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 である。

制約

  • 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 つ以上存在する
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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 番目のクエリに対する答えをこの順に空白区切りで出力せよ。

入力例 1

5 2
2 3 3
5 4 3

出力例 1

3 -1 -1 -1 -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 となります。

入力例 2

3 0

出力例 2

-1 -1 -1

入力例 3

8 5
6 7 3
8 1 7
4 5 1
7 2 1
6 2 4

出力例 3

1 -1 -1 -1 -1 -1 -1 8

Score: 525 points

Problem Statement

There are N people, numbered 1 to N.

A competition was held among these N people, and they were ranked accordingly. The following information is given about their ranks:

  • Each person has a unique rank.
  • For each 1 \leq i \leq M, if person A_i is ranked x-th and person B_i is ranked y-th, then x - y = C_i.

The given input guarantees that there is at least one possible ranking that does not contradict the given information.

Answer N queries. The answer to the i-th query is an integer determined as follows:

  • If the rank of person i can be uniquely determined, return that rank. Otherwise, return -1.

Constraints

  • 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)
  • There is at least one possible ranking that does not contradict the given information.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

Print the answers to the 1-st, 2-nd, \ldots, N-th queries in this order, separated by spaces.

Sample Input 1

5 2
2 3 3
5 4 3

Sample Output 1

3 -1 -1 -1 -1

Let X_i be the rank of person i. Then, (X_1, X_2, X_3, X_4, X_5) could be (3, 4, 1, 2, 5) or (3, 5, 2, 1, 4).

Therefore, the answer to the 1-st query is 3, and the answers to the 2-nd, 3-rd, 4-th, and 5-th queries are -1.

Sample Input 2

3 0

Sample Output 2

-1 -1 -1

Sample Input 3

8 5
6 7 3
8 1 7
4 5 1
7 2 1
6 2 4

Sample Output 3

1 -1 -1 -1 -1 -1 -1 8