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\le50\,000$，$1\le m\le200\,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