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