Фабрика 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