E. Пастушеские странности
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В стране Бурении есть n пастбищ, но нет дорог, их соединяющих. Конечно, это ужасная ситуация, поэтому Кевин Сан планирует исправить её, построив m двунаправленных дорог. Каждая дорога соединит какую пару пастбищ. Для того чтобы перемещение по дорогам было более эффективным, он также планирует замостить некоторые из этих новых дорог булыжником.

Кевин очень дотошен в вопросе мощения путей. Так как он любит нечётные числа, то хочет, чтобы к каждому пастбищу вело нечётное число мощеных дорог. Назовём замощение дорог солнечным, если каждому пастбищу инцидентно нечётное количество замощёных дорог. Кроме того, короткие дороги нравятся Кевину больше, чем длинные, поэтому он хочет, чтобы самая длинная мощёная дорога была как можно короче. После добавления очередной дороги Кевин хочет знать, может ли он добиться солнечного замощения дорог Бурении, и если это так, то надо найти минимальную возможную длину самой длинной дороги, которую он замостит.

Входные данные

Первая строка входных данных содержит два числа n и m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 300 000) — количество пастбищ и дорог соответственно.

Следующие m строк содержат по три целых числа ai, bi и li. Они описывают i-ю дорогу, соединяющую пастбища ai и bi (1 ≤ ai, bi ≤ n; ai ≠ bi) и имеющую длину li (1 ≤ li ≤ 109).

Дороги приведены в том порядке, в котором они добавляются.

Выходные данные

Выведите m целых чисел, i-е из которых обозначает минимальную возможную длину самой длинной дороги в солнечном замощении после добавления первых i дорог. Если не существует такого замощения, что каждое пастбище инцидентно нечётному количеству мощёных дорог, то выведите  - 1.

Обратите внимание, что каждый раз рассматривается только гипотетическое замощение — ваш ответ после добавления i-й дороги не должен никак зависеть от ваших предыдущих ответов.

Примеры
Входные данные
4 4
1 3 4
2 4 8
1 2 2
3 4 3
Выходные данные
-1
8
8
3
Входные данные
3 2
1 2 3
2 3 4
Выходные данные
-1
-1
Входные данные
4 10
2 1 987
3 2 829
4 1 768
4 2 608
3 4 593
3 2 488
4 2 334
2 1 204
1 3 114
1 4 39
Выходные данные
-1
-1
829
829
768
768
768
488
334
204
Примечание

В первом примере после добавления i-й дороги пути Кевин должен вымостить следующие из них:

  1. Никакой набор дорог не подходит.
  2. Дорога номер 1 (длина 4) и номер 2 (длина 8).
  3. Дорога номер 1 (длина 4) и номер 2 (длина 8).
  4. Дорога номер 3 (длина 2) и номер 4 (длина 3).

Во втором примере нет ни одного солнечного замощения.