Score: $525$ points

问题陈述

有 $N$ 个人，编号为 $1$ 到 $N$。

在这些人之间举行了一场比赛，并且他们已经根据比赛结果进行了排名。关于他们的排名，给出了以下信息：

• 每个人都有一个独特的排名。
• 对于每个 $1 \leq i \leq M$，如果第 $A_i$ 个人排名第 $x$，第 $B_i$ 个人排名第 $y$，那么 $x - y = C_i$。

给定的输入保证至少存在一种排名，它不会与给定的信息相矛盾。

回答 $N$ 个查询。第 $i$ 个查询的答案如下确定：

• 如果可以唯一确定第 $i$ 个人的排名，返回该排名。否则，返回 $-1$。

以上为大语言模型 kimi 翻译，仅供参考。

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