CF1430G.Yet Another DAG Problem

You are given a directed acyclic graph (a directed graph that does not contain cycles) of $n$ vertices and $m$ arcs. The $i$-th arc leads from the vertex $x_i$ to the vertex $y_i$ and has the weight $w_i$.

Your task is to select an integer $a_v$ for each vertex $v$, and then write a number $b_i$ on each arcs $i$ such that $b_i = a_{x_i} - a_{y_i}$. You must select the numbers so that:

• all $b_i$ are positive;
• the value of the expression $\sum \limits_{i = 1}^{m} w_i b_i$ is the lowest possible.

It can be shown that for any directed acyclic graph with non-negative $w_i$, such a way to choose numbers exists.

给你一个包含 $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$ 非负的有向无环图，总存在满足上述要求的选取方式。

The first line contains two integers $n$ and $m$ ($2 \le n \le 18$; $0 \le m \le \dfrac{n(n - 1)}{2}$).

Then $m$ lines follow, the $i$-th of them contains three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i, y_i \le n$, $1 \le w_i \le 10^5$, $x_i \ne y_i$) — the description of the $i$-th arc.

It is guaranteed that the lines describe $m$ arcs of a directed acyclic graph without multiple arcs between the same pair of vertices.

第一行包含两个整数 $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$ 条有向边的描述。

保证这些行描述了一个有向无环图（DAG）的 $m$ 条边，且任意一对顶点之间不存在重边。

Print $n$ integers $a_1$, $a_2$, ..., $a_n$ ($0 \le a_v \le 10^9$), which must be written on the vertices so that all $b_i$ are positive, and the value of the expression $\sum \limits_{i = 1}^{m} w_i b_i$ is the lowest possible. If there are several answers, print any of them. It can be shown that the answer always exists, and at least one of the optimal answers satisfies the constraints $0 \le a_v \le 10^9$.

输出 $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$。