Fabryka Little Q kupiła niedawno $n$ nowych urządzeń, ponumerowanych $1,2,\ldots,n$.

W fabryce jest $n$ pracowników, ponumerowanych $1,2,\ldots,n$. Każdego pracownika można przydzielić do co najwyżej jednego urządzenia, a żadnego urządzenia nie można przydzielić wielu pracownikom. Jeśli Little Q przydzieli $i$-tego pracownika do $j$-tego urządzenia, przyniosą oni zysk $p_{i,j}$. Pracownicy nie są jednak zbyt doświadczeni, więc większość wartości w macierzy $p$ jest równa zeru, z wyjątkiem $m$ komórek. Otrzymasz informacje o tych $m$ komórkach.

Dla każdego $k$ ($1\le k\le n$) znajdź $k$ par pracowników i urządzeń, a następnie przydziel pracowników do tych urządzeń tak, aby łączny zysk z tych $k$ par był jak największy.

Wejście

Wejście zawiera tylko jeden przypadek testowy.

Pierwszy wiersz zawiera dwie liczby całkowite $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$), oznaczające liczbę pracowników/nowych urządzeń oraz liczbę specjalnych komórek w $p$.

Każdy z kolejnych $m$ wierszy zawiera trzy liczby całkowite $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$), oznaczające $p_{u_i,v_i}=w_i$. Każda para $u_i,v_i$ zostanie opisana co najwyżej raz.

Wyjście

Wypisz $n$ wierszy. W $k$-tym z nich ($1\le k\le n$) wypisz liczbę całkowitą oznaczającą największy możliwy łączny zysk z $k$ par pracowników i urządzeń.

Przykład

Wejście 1

2 3
1 1 4
1 2 2
2 1 3

Wyjście 1

4
5

Wejście 2

2 3
1 1 5
1 2 2
2 1 2

Wyjście 2

5
5