CF1430G Yet Another DAG Problem

给定一个包含 $n$ 个顶点和 $m$ 条弧的有向无环图。第 $i$ 条弧从顶点 $x_i$ 指向顶点 $y_i$，其权重为 $w_i$。 你的任务是为每个顶点 $v$ 选择一个整数 $a_v$，然后在每条弧 $i$ 上标注一个数字 $b_i$，满足 $b_i = a_{x_i} - a_{y_i}$。选择数字时必须满足以下条件： - 所有 $b_i$ 均为正数； - 表达式 $\sum \limits_{i = 1}^{m} w_i b_i$ 的值尽可能小。 可以证明，对于任何具有非负 $w_i$ 的有向无环图，都存在这样的数字选择方式。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 18$；$0 \le m \le \dfrac{n(n - 1)} {2}$）。 随后 $m$ 行，第 $i$ 行包含三个整数 $x_i$、$y_i$ 和 $w_i$（$1 \le x_i, y_i \le n$，$1 \le w_i \le 10^5$，$x_i \ne y_i$）表示第 $i$ 条有向边的描述。 数据保证这些行描述的是 $m$ 条有向无环图的边，且同一对顶点之间不存在多条边。

输出 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$0 \le a_v \le 10^9$），这些整数必须写在顶点上，使得所有 $b_i$ 均为正数，且表达式 $\sum \limits_{i = 1}^{m} w_i b_i$ 的值尽可能小。若有多个解，输出其中任意一个。可以证明答案始终存在，且至少有一个最优解满足约束条件 $0 \le a_v \le 10^9$。