A fábrica de Little Q comprou recentemente $n$ novos equipamentos, numerados de $1,2,\ldots,n$.

Há $n$ trabalhadores na fábrica, numerados de $1,2,\ldots,n$. Cada trabalhador pode ser atribuído a, no máximo, um equipamento, e nenhum equipamento pode ser atribuído a vários trabalhadores. Se Little Q atribuir o trabalhador $i$ ao equipamento $j$, eles produzirão um lucro de $p_{i,j}$. Porém, estes trabalhadores não têm muita experiência, por isso a maioria dos valores da matriz $p$ é zero, exceto em $m$ células. Essas $m$ células serão fornecidas.

Para cada $k$ ($1\le k\le n$), encontre $k$ pares de trabalhadores e equipamentos e atribua os trabalhadores a esses equipamentos de modo que o lucro total desses $k$ pares seja máximo.

Entrada

A entrada contém apenas um caso de teste.

A primeira linha contém dois inteiros $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$), que indicam o número de trabalhadores/novos equipamentos e o número de células especiais em $p$.

Cada uma das $m$ linhas seguintes contém três inteiros $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$), indicando que $p_{u_i,v_i}=w_i$. Cada par $u_i,v_i$ será descrito no máximo uma vez.

Saída

Escreva $n$ linhas. A linha $k$ ($1\le k\le n$) deve conter um inteiro que indique o maior lucro total possível para $k$ pares de trabalhadores e equipamentos.

Exemplos

Entrada 1

2 3
1 1 4
1 2 2
2 1 3

Saída 1

4
5

Entrada 2

2 3
1 1 5
1 2 2
2 1 2

Saída 2

5
5