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