ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2015

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Урбанистика

Ограничение времени: 1.5 секунды
Ограничение памяти: 128 МБ
Андроид Вася делает проект по урбанистике. Цель проекта — улучшить инфраструктуру города, в котором он живет.
Сейчас город представляет собой n районов, некоторые из которых соединены дорогами. Используя эти дороги, можно добраться на автомобиле из любого района в любой другой. Вася думает, что слишком большое количество дорог в городе побуждает горожан пользоваться личным автотранспортом вместо того, чтобы ходить пешком или ездить на велосипеде. Он хочет закрыть для движения автомобилей максимальное число дорог, превратив их в пешеходные бульвары. Естественно, после этого должна сохраниться возможность добраться на автомобиле по дорогам из любого района в любой.
Сейчас за пользование каждой дорогой автомобилисты платят деньги, причем цены за использование разных дорог могут сильно отличаться. Вася думает, что если оставить открытыми для проезда автомобилей как очень дешевые, так и очень дорогие дороги, то это может повысить социальную напряженность в городе. Поэтому он хочет минимизировать разницу между стоимостью проезда по самой дорогой и самой дешевой дороге среди тех, что останутся открытыми. Помогите Васе выбрать дороги, которые нужно сохранить.

Исходные данные

В первой строке даны целые числа n и m — количество районов и дорог соответственно (2 ≤ n ≤ 50000; n − 1 ≤ m ≤ 50000). В следующих m строках даны тройки целых чисел ai, bi и ci, означающие, что между районами ai и bi есть дорога стоимости ci (1 ≤ ai, bin; aibi; 1 ≤ ci ≤ 109). Между любой парой районов может быть несколько дорог.

Результат

В единственной строке выведите последовательность номеров дорог, которые стоит оставить открытыми для проезда. Дороги нумеруются целыми числами от 1 до m в том порядке, в котором они были описаны во входных данных. Если возможных решений несколько, выведите любое из них.

Примеры

исходные данныерезультат
3 3
1 2 1
2 3 3
3 1 4
2 3
4 5
1 2 1
2 3 1
1 3 2
1 4 2
2 4 1
1 2 5
Автор задачи: Никита Бурлаков
Источник задачи: XIX Открытый чемпионат Урала по спортивному программированию (апрель, 2015)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2055. Урбанистика