Little Q 的工廠最近購買了 $n$ 臺新設備，編號為 $1,2,\ldots,n$。

工廠裡有 $n$ 名工人，編號為 $1,2,\ldots,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\le5$），表示 $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