Little Q の工場は最近、$1,2,\ldots,n$ と番号の付いた $n$ 台の新しい設備を購入しました。

工場には $1,2,\ldots,n$ と番号の付いた $n$ 人の作業員がいます。各作業員は高々 1 台の設備に割り当てることができ、1 台の設備に複数の作業員を割り当てることはできません。Little Q が $i$ 番目の作業員を $j$ 番目の設備に割り当てると、$p_{i,j}$ の利益が得られます。しかし、これらの作業員はあまり経験豊富ではないため、行列 $p$ の値は $m$ 個の要素を除いてほとんどがゼロです。この $m$ 個の要素が与えられます。

各 $k$（$1\le k\le n$）について、作業員と設備の組を $k$ 組選び、作業員をそれぞれの設備に割り当てたときの利益の合計を最大にしてください。

入力

入力は 1 つのテストケースのみからなります。

最初の行には整数 $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$ の組は高々 1 回記述されます。

出力

$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