给定一个由 $$$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$$$。
示例
输入 #1
3 2 2 1 4 1 3 2
输出 #1
1 2 0
输入 #2
5 4 1 2 1 2 3 1 1 3 6 4 5 8
输出 #2
43 42 41 1337 1336
输入 #3
5 5 1 2 1 2 3 1 3 4 1 1 5 1 5 4 10
输出 #3
4 3 2 1 2