Максимальный взвешенный разрез

Дан неориентированный взвешенный граф.

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

Формат входных данных

В первой строке записаны два целых числа:

N M

Далее следуют M строк. Каждая строка содержит:

u v w

где u и v — номера вершин, а w — положительный вес ребра.

Вершины нумеруются от 1 до N.

Формат выходных данных

Выведите N чисел, каждое из которых равно 0 или 1.

Число на позиции i задаёт группу вершины i.

Числа можно выводить через пробел или перевод строки.

Целевая функция

Пусть W — сумма весов всех рёбер, а C — вес полученного разреза.

Checker вычисляет:

objective = W - C

Чем меньше objective, тем лучше решение.

Любое разбиение всех вершин на две группы является корректным.