L'usine de Little Q a récemment acheté $n$ nouveaux équipements, numérotés $1,2,\ldots,n$.

L'usine compte $n$ ouvriers, numérotés $1,2,\ldots,n$. Chaque ouvrier peut être affecté à au plus un équipement, et aucun équipement ne peut être affecté à plusieurs ouvriers. Si Little Q affecte le $i$-ème ouvrier au $j$-ème équipement, ils rapporteront un bénéfice de $p_{i,j}$. Cependant, ces ouvriers ne sont pas très expérimentés, donc la plupart des valeurs de la matrice $p$ sont nulles, à l'exception de $m$ cases. Ces $m$ cases vous seront données.

Pour chaque $k$ ($1\le k\le n$), trouvez $k$ paires d'ouvriers et d'équipements, puis affectez les ouvriers à ces équipements de façon à maximiser le bénéfice total de ces $k$ paires.

Entrée

L'entrée ne contient qu'un seul cas de test.

La première ligne contient deux entiers $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$), indiquant le nombre d'ouvriers/de nouveaux équipements et le nombre de cases particulières de $p$.

Chacune des $m$ lignes suivantes contient trois entiers $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$), indiquant que $p_{u_i,v_i}=w_i$. Chaque paire $u_i,v_i$ est décrite au plus une fois.

Sortie

Affichez $n$ lignes. La $k$-ème ($1\le k\le n$) doit contenir un entier indiquant le bénéfice total maximal possible pour $k$ paires d'ouvriers et d'équipements.

Exemples

Entrée 1

2 3
1 1 4
1 2 2
2 1 3

Sortie 1

4
5

Entrée 2

2 3
1 1 5
1 2 2
2 1 2

Sortie 2

5
5