推测名次

题目描述

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

这 $N$ 个人参加了一场比赛,并获得了相应的名次。关于他们的名次,给出了以下信息:

• 每个人的名次互不相同。
• 对于每个 $1 \le i \le M$,若人 $A_i$ 的名次为 $x$,人 $B_i$ 的名次为 $y$,则 $x - y = C_i$。

给定的输入保证至少存在一种与给定信息不矛盾的名次排列。

回答 $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$ 个询问的答案,用空格分隔。

样例

5 2
2 3 3
5 4 3

3 -1 -1 -1 -1

设 $X_i$ 为人 $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$。

3 0

-1 -1 -1

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

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

数据范围

• $2 \le N \le 16$
• $0 \le M \le \frac{N(N - 1)}{2}$
• $1 \le A_i, B_i \le N$
• $1 \le C_i \le N - 1$
• 若 $i \neq j$,则 $(A_i, B_i) \neq (A_j, B_j)$
• 至少存在一种与给定信息不矛盾的名次排列
• 输入中的所有值均为整数