Модуль: Поиск в глубину. DFS


Задача

19 /19


Breaking News


Задача

Жизнь завода по производству олимпиадных задач монотонна и однообразна: каждый день происходит одно и то же, вечера похожи как две снежинки и каждое утро всё начинается сначала - ничего не меняется на заводе по производству олимпиадных задач.
В частности, давно известно, когда в течение дня пара сотрудников встречается между собой.
При встрече сотрудники делятся друг с другом новостями.
Утром перед работой сотрудник номер 1 узнал нежелательную новость. Конечно же, он делится с ней при встрече со всеми остальными сотрудниками и они тоже узнают новость и начинаются делиться ей с другими. Если встречаются два сотрудника и один из них знает новость, то начиная с этого момента второй из них также знает новость. Ни один сотрудник не может встречаться с двумя или более сотрудниками одновременно (из соображений секретности). Пара сотрудников может встречаться несколько раз в течение дня.
Вы можете помешать ровно одной встрече за весь день. Выберите такую встречу, отмена которой приведёт к тому, что как можно меньше сотрудников завода узнают новость.

Входные данные
В первой строке входного файла задано два целых числа N (2 ≤ N ≤ 1000) и D (1 ≤ D ≤ 100000) — количество сотрудников и встреч соответственно. В следующих D строках заданы описания встреч. Каждое описание встречи состоит из трех
чисел Ai, Bi и Ti (1 ≤ Ai, Bi ≤ N, 1 ≤ Ti ≤ 109) — пара номеров сотрудников и время встречи.

Выходные данные
Выведите описание встречи, которую необходимо отменить в том же формате, который используется во входных данных. Если ответов несколько — выведите любой.
Примеры
Входные данные Выходные данные
1 4 5
2 3 1
1 2 4
4 2 110
2 3 5
3 4 4
1 2 4

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w646
Комментарий учителя