La fábrica de Little Q compró recientemente $n$ equipos nuevos, numerados $1,2,\ldots,n$.

Hay $n$ trabajadores en la fábrica, numerados $1,2,\ldots,n$. Cada trabajador puede asignarse como máximo a un equipo, y ningún equipo puede asignarse a varios trabajadores. Si Little Q asigna al trabajador $i$ al equipo $j$, producirán un beneficio de $p_{i,j}$. Sin embargo, estos trabajadores no tienen mucha experiencia, por lo que la mayoría de los valores de la matriz $p$ son cero, salvo $m$ celdas. Se te darán esas $m$ celdas.

Para cada $k$ ($1\le k\le n$), encuentra $k$ parejas de trabajadores y equipos y asigna los trabajadores a esos equipos de modo que el beneficio total de las $k$ parejas sea máximo.

Entrada

La entrada contiene un único caso de prueba.

La primera línea contiene dos enteros $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$), que indican el número de trabajadores/equipos nuevos y el número de celdas especiales de $p$.

Cada una de las siguientes $m$ líneas contiene tres enteros $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$), que indican que $p_{u_i,v_i}=w_i$. Cada pareja $u_i,v_i$ se describe como máximo una vez.

Salida

Imprime $n$ líneas. La línea $k$ ($1\le k\le n$) debe contener un entero: el máximo beneficio total posible para $k$ parejas de trabajadores y equipos.

Ejemplos

Entrada 1

2 3
1 1 4
1 2 2
2 1 3

Salida 1

4
5

Entrada 2

2 3
1 1 5
1 2 2
2 1 2

Salida 2

5
5