Byteman 望向窗外，看到他家门前的车站停着一辆老式电车。他试图拍张照片加入他的老式交通工具照片收藏，但还没等他拿到相机，电车就开走了。

Byteman 住在 Bytetown。城里有 $n$ 个路口，编号从 $1$ 到 $n$，每个路口附近都有一个电车站。那里的公共交通非常准时，电车会在整分钟到达车站。因此，他决定每分钟都望向窗外，希望那辆独特的电车能再次出现在车站。过了一段时间，这变得很烦人，Byteman 决定寻找一个更聪明的解决方案。他拿出一张 Bytetown 的地图开始分析（这并不容易，因为他每分钟都要望向窗外）。最终，他将相机设置为每 $T$ 分钟拍摄一次车站。他选择的 $T$ 是满足以下条件的最大整数：从老式电车第一次出现开始，每 $T$ 分钟拍摄一次车站，无论电车走哪条路线，都不会错过电车的任何一次到达。

这个结果让 Byteman 感到非常有趣，于是他开始思考，如果他住在另一个第 $j$ 个电车站旁边，会得到什么结果（记为 $T_{j}$）。因此，$T_{j}$ 是满足以下条件的最大整数：如果 Byteman 住在第 $j$ 个路口旁边，且电车在第 0 分钟出现在车站，那么无论其路线如何，它之后所有出现在车站的时间点都必须是 $T_{j}$ 的倍数。如果第 $j$ 个路口没有轨道起点，或者离开该路口的电车永远不会返回，则 $T_{j} = -1$。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100\,000$)，用空格分隔，分别表示城中的路口数量和连接它们的线路数量。路口编号从 $1$ 到 $n$。接下来的 $m$ 行描述了 Bytetown 的电车网络。其中第 $i$ 行包含三个整数 $a_{i}, b_{i}, c_{i}$ ($1 \le a_{i}, b_{i} \le n$, $1 \le c_{i} \le 10\,000$)，用空格分隔。每个三元组表示电车可以从路口 $a_{i}$ 在 $c_{i}$ 分钟内到达路口 $b_{i}$。所有轨道都是单向的，但可能存在从 $a_{i}$ 到 $b_{i}$ 以及从 $b_{i}$ 到 $a_{i}$ 的双向轨道。也可能出现 $a_{i} = b_{i}$ 的情况（环线）。给定方向上两个路口之间最多只有一条连接。

电车在车站停留的时间可以忽略不计。此外，我们假设电车会一直行驶（直到到达死胡同，或者如果永远达不到死胡同则无限行驶）。

输出格式

向标准输出打印 $n$ 个整数，每行一个。第 $j$ 行应包含数字 $T_{j}$。

样例

输入 1

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

输出 1

-1
2
2
10
10
10
-1

说明 1