Магические сферы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
magic.in
вывод
magic.out

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

Всего существует m пар связанных сфер, при этом каждая связь обладает определенной силой e. Пусть r  — это сумма по всем силам связи. Баланс сил считается успешно восстановленным, если суммарная сила связи между сферами, заряженными одним типом магии, не больше, чем r / 2.

Помогите Стрэнджу найти правильный тип магии для каждой сферы.

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

В первой строке заданы числа n и m  — количество сфер и количество связей (1 ≤ n, m ≤ 105).

Далее следуют m строк. В каждой записаны числа a, b и e  — связь между сферой a и b с силой равной e (1 ≤ a, b ≤ n; 1 ≤ e ≤ 109).

Гарантируется, что сферы не связаны сами с собой и не существует более одной связи между каждой парой сфер.

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

Если ответ существует, требуется вывести n чисел, где i-ое число равно 1, если сфера i заряжена темной магией, либо i-ое число равно 0, если сфера i заряжена светлой магией. Если ответа не существует, выведите Nema.

Примеры

Входные данные
3 2
1 2 2
2 3 3
Выходные данные
0 0 1
Входные данные
5 6
1 2 1
2 3 1
3 4 5
5 1 2
2 5 2
3 1 3
Выходные данные
0 1 1 0 0 

Примечание

В первом примере значение r = 5 и сумма ребер одного цвета равна 2. Раскраска подходит, потому что сумма ребер одного цвета 2 меньше, чем половина суммы всех ребер 2.5.