Фабрика Little Q нещодавно придбала $n$ одиниць нового обладнання, пронумерованих $1,2,\ldots,n$.

На фабриці є $n$ робітників, пронумерованих $1,2,\ldots,n$. Кожному робітникові можна призначити не більше однієї одиниці обладнання, і жодну одиницю обладнання не можна призначити кільком робітникам. Якщо Little Q призначить $i$-го робітника на $j$-ту одиницю обладнання, вони принесуть прибуток $p_{i,j}$. Однак ці робітники не дуже досвідчені, тому більшість значень у матриці $p$ дорівнюють нулю, за винятком $m$ клітинок. Вам буде надано ці $m$ клітинок.

Для кожного $k$ ($1\le k\le n$) знайдіть $k$ пар робітників та одиниць обладнання і призначте робітників на це обладнання так, щоб сумарний прибуток цих $k$ пар був максимальним.

Вхідні дані

Вхідні дані містять лише один тестовий випадок.

Перший рядок містить два цілі числа $n,m$ ($1\le n\le50\,000$, $1\le m\le200\,000$), що позначають кількість робітників/одиниць нового обладнання та кількість особливих клітинок у $p$.

Кожен із наступних $m$ рядків містить три цілі числа $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le5$), що означають $p_{u_i,v_i}=w_i$. Кожну пару $u_i,v_i$ буде описано не більше одного разу.

Вихідні дані

Виведіть $n$ рядків. У $k$-му рядку ($1\le k\le n$) має бути ціле число, що позначає найбільший можливий сумарний прибуток для $k$ пар робітників та одиниць обладнання.

Приклади

Вхідні дані 1

2 3
1 1 4
1 2 2
2 1 3

Вихідні дані 1

4
5

Вхідні дані 2

2 3
1 1 5
1 2 2
2 1 2

Вихідні дані 2

5
5