Мережеві війни#4591
Комп'ютерна мережа Байтландії складається з комп'ютерів, з'єднаних оптоволоконними кабелями. Кожен кабель з'єднує рівно два комп'ютери і може передавати дані в обох напрямках. У мережі є два особливо важливі комп'ютери: один надає доступ до інтернету, а інший під'єднаний до президентської резиденції.
Комп'ютеру, під'єднаному до президентської резиденції, призначено номер , а комп'ютеру з виходом в інтернет — номер .
Нещодавно компанія Max Traffic вирішила отримати контроль над деякими з'єднаннями, щоб мати можливість відстежувати всі передачі даних з інтернету до користувачів у президентській резиденції. Звісно, Max Traffic прагне контролювати такий набір з'єднань, щоб усі дані, які переміщуються від інтернету до резиденції, обов'язково проходили хоча б через одне з контрольованих з'єднань.
Щоб здійснити цей план, компанія повинна викупити вибрані з'єднання у їх поточних власників. Кожне з'єднання має свою ціну викупу. Оскільки основний бізнес компанії — не шпигунство, а надання інтернет-послуг, вони хочуть мінімізувати загальні витрати на викуп. Якщо компанія купить з'єднань загальною вартістю , необхідно мінімізувати значення .
У першому рядку містяться два цілих числа: - (2 \leq n \leq 100): кількість комп'ютерів. - (1 \leq m \leq 400): кількість оптоволоконних кабелів.
Наступні рядків описують кабелі: кожен кабель задається трьома числами — номерами двох комп'ютерів, які він з'єднує, та ціною викупу. Всі ціни додатні та не перевищують 10^7.
Жодні двоє комп'ютерів не з'єднані більш ніж одним кабелем, і жоден кабель не з'єднує комп'ютер сам із собою. Гарантується, що мережа є зв'язаною: дані можна передати між будь-якими двома комп'ютерами через кабелі.
Виведіть у першому рядку кількість з'єднань, які потрібно викупити. У другому рядку — номери цих з'єднань. З'єднання нумеруються з у тому порядку, в якому вони наведені у вхідному файлі.
Приклад 1