Die Fabrik von Little Q hat kürzlich $n$ neue Geräte gekauft, die mit $1,2,\ldots,n$ nummeriert sind.

In der Fabrik gibt es $n$ Arbeiter, die mit $1,2,\ldots,n$ nummeriert sind. Jeder Arbeiter kann höchstens einem Gerät zugeteilt werden, und kein Gerät kann mehreren Arbeitern zugeteilt werden. Wenn Little Q den $i$-ten Arbeiter dem $j$-ten Gerät zuteilt, erzielen sie einen Gewinn von $p_{i,j}$. Diese Arbeiter sind jedoch nicht besonders erfahren, sodass die meisten Werte in der Matrix $p$ null sind, mit Ausnahme von $m$ Einträgen. Diese $m$ Einträge werden dir gegeben.

Finde nun für jedes $k$ ($1\le k\le n$) genau $k$ Paare aus Arbeitern und Geräten und teile die Arbeiter diesen Geräten so zu, dass der Gesamtgewinn dieser $k$ Paare maximal ist.

Eingabe

Die Eingabe enthält nur einen Testfall.

Die erste Zeile enthält zwei ganze Zahlen $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$), die die Anzahl der Arbeiter/neuen Geräte und die Anzahl der besonderen Einträge in $p$ angeben.

Jede der folgenden $m$ Zeilen enthält drei ganze Zahlen $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$), die $p_{u_i,v_i}=w_i$ angeben. Jedes Paar $u_i,v_i$ wird höchstens einmal beschrieben.

Ausgabe

Gib $n$ Zeilen aus. Die $k$-te Zeile ($1\le k\le n$) soll eine ganze Zahl enthalten, die den maximal möglichen Gesamtgewinn für $k$ Paare aus Arbeitern und Geräten angibt.

Beispiele

Eingabe 1

2 3
1 1 4
1 2 2
2 1 3

Ausgabe 1

4
5

Eingabe 2

2 3
1 1 5
1 2 2
2 1 2

Ausgabe 2

5
5