Pabrik Little Q baru-baru ini membeli $n$ peralatan baru, yang diberi nomor $1,2,\ldots,n$.

Ada $n$ pekerja di pabrik, yang diberi nomor $1,2,\ldots,n$. Setiap pekerja dapat ditugaskan ke paling banyak satu peralatan, dan tidak ada peralatan yang dapat ditugaskan kepada beberapa pekerja. Jika Little Q menugaskan pekerja ke-$i$ ke peralatan ke-$j$, mereka akan menghasilkan keuntungan $p_{i,j}$. Namun, para pekerja ini tidak terlalu berpengalaman, sehingga sebagian besar nilai dalam matriks $p$ bernilai nol, kecuali $m$ sel. Anda akan diberikan $m$ sel ini.

Untuk setiap $k$ ($1\le k\le n$), carilah $k$ pasangan pekerja dan peralatan, lalu tugaskan pekerja ke peralatan tersebut sehingga total keuntungan dari $k$ pasangan itu maksimum.

Masukan

Masukan hanya berisi satu kasus uji.

Baris pertama berisi dua bilangan bulat $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$), yang menyatakan jumlah pekerja/peralatan baru dan jumlah sel khusus dalam $p$.

Masing-masing dari $m$ baris berikutnya berisi tiga bilangan bulat $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$), yang menyatakan $p_{u_i,v_i}=w_i$. Setiap pasangan $u_i,v_i$ akan dijelaskan paling banyak sekali.

Keluaran

Keluarkan $n$ baris, dengan baris ke-$k$ ($1\le k\le n$) berisi sebuah bilangan bulat yang menyatakan total keuntungan maksimum yang mungkin untuk $k$ pasangan pekerja dan peralatan.

Contoh

Masukan 1

2 3
1 1 4
1 2 2
2 1 3

Keluaran 1

4
5

Masukan 2

2 3
1 1 5
1 2 2
2 1 2

Keluaran 2

5
5