问题描述

有 N 个人，编号从 1 到 ​N​。

在这 N 个人之间举行了一场竞赛，且他们被依次排名。给出以下关于他们排名的信息：

• 每个人有一个独特的排名。
• 对于每个 ​1 ≤ i ≤ M​，如果第 Aᵢ 个人的排名为 ​x​，第 Bᵢ 个人的排名为 ​y​，那么 ​x - y = Cᵢ​。

给定的输入保证至少存在一种不会与给定信息冲突的排名。

现在，要求回答 N 个查询。第 i 个查询的答案为一个整数，按如下规则确定：

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

约束条件

• 2 ≤ N ≤ 16
• 0 ≤ M ≤ 2N(N-1)
• 1 ≤ Aᵢ, Bᵢ ≤ N
• 1 ≤ Cᵢ ≤ N-1
• (Aᵢ, Bᵢ) ≠ (Aⱼ, Bⱼ) （​i ≠ j​）
• 至少存在一种不会与给定信息冲突的排名。
• 所有输入值均为整数。

输入格式

从标准输入中按以下格式给出输入：

N M
A₁ B₁ C₁
A₂ B₂ C₂
...
Aₘ Bₘ Cₘ

输出格式

输出 1 到 N 个查询的答案，以空格分隔。

示例输入 1

5 2
2 3 3
5 4 3

示例输出 1

3 -1 -1 -1 -1

​解释​： 令 Xᵢ 表示第 i 个人的排名。那么，(X₁, X₂, X₃, X₄, X₅) 可能是 (3, 4, 1, 2, 5) 或 ​**(3, 5, 2, 1, 4)**​。

因此，第 1 个查询的答案是 ​3​，第 2 到第 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

思路与解题

这个问题需要通过给定的排名差来推理每个人的排名。由于 N 最大为 ​16​，可以尝试用穷举的方式生成所有可能的排名，然后验证它们是否符合所有的约束条件。

具体步骤如下：

1. 枚举所有可能的排名（最多 16! 种可能，但因为约束条件，实际可能较少）。
2. 对于每个排名，检查是否符合所有的 M 条约束。
3. 对于每个查询，判断该人的排名是否可以唯一确定，如果可以，返回该排名，否则返回 ​**-1**​。