Задача . D. Duff в мафии

Duff — одна из глав мафии в своей стране Andarz Gu. В Andarz Gu n городов (пронумерованных от 1 до n), соединенных m двусторонними дорогами (пронумерованными от 1 до m).

У каждой дороги есть два специальных параметра — время её разрушения и цвет. i-я дорога соединяет города v_i и u_i, её цвет — c_i, а время разрушения — t_i.

Мафия хочет разрушить паросочетание в Andarz Gu. Паросочетание — это подмножество дорог, такое, что никакие две дороги в этом подмножестве не имеют один и тот же город в качестве конца. Дороги можно разрушать параллельно, то есть, время полного разрушения набора дорог определяется как максимум среди времен разрушения всех дорог в наборе.

Имеются два условия:

1. Оставшиеся дороги образуют в правильную раскраску.
2. Время разрушения этого паросочетания как можно меньше.

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

У мафии нет программиста в штате. Поэтому Duff попросила вас помочь ей. Пожалуйста, помогите ей и определите, какое паросочетание надо уничтожить, чтобы удовлетворить вышеописанным условиям, либо скажите, что это невозможно.