28965번 - Магические сферы 스페셜 저지다국어

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

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

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

В первой строке заданы числа $n$ и $m$ --- количество сфер и количество связей ($1 \le n, m \le 10^5$).

Далее следуют $m$ строк. В каждой записаны числа $a$, $b$ и $e$ --- связь между сферой $a$ и $b$ с силой равной $e$ ($1 \le a, b \le n$; $1 \le e \le 10^9$).

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

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

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