Little Q 的工厂最近购买了 $n$ 件新设备，编号为 $1, 2, \dots, n$。

工厂里有 $n$ 名工人，编号为 $1, 2, \dots, n$。每名工人最多只能分配到一件设备，且每件设备最多只能分配给一名工人。如果 Little Q 将第 $i$ 名工人分配给第 $j$ 件设备，他们将带来 $p_{i,j}$ 的利润。然而，这些工人经验不足，因此矩阵 $p$ 中的大多数值都为零，只有 $m$ 个单元格不为零。你将获得这 $m$ 个单元格的信息。

现在请对于每一个 $k$ ($1 \le k \le n$)，找出 $k$ 对工人和设备，并将工人分配给这些设备，使得这 $k$ 对的总利润最大化。

输入格式

输入包含单个测试用例。

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50\,000, 1 \le m \le 200\,000$)，分别表示工人和设备的数量以及矩阵 $p$ 中特殊单元格的数量。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 5$)，表示 $p_{u_i,v_i} = w_i$。每一对 $u_i$ 和 $v_i$ 最多只会被描述一次。

输出格式

输出 $n$ 行，第 $k$ 行 ($1 \le k \le n$) 包含一个整数，表示分配 $k$ 对工人和设备时可能获得的最大总利润。

样例

样例输入 1

2 3
1 1 4
1 2 2
2 1 3

样例输出 1

4
5

样例输入 2

2 3
1 1 5
1 2 2
2 1 2

样例输出 2

5
5