Пересылка файлов
(Время: 1 сек. Память: 16 Мб Сложность: 49%)
В постиндустриальную эпоху основной ценностью является информация. Поэтому особо важен контроль над каналами передачи информации. В одной стране все каналы связи контролируются государством.
Перед ИТ-отделом одной достаточно крупной фирмы, занимающейся консалтингом в области инновационных технологий, была поставлена задача распространить некий файл по филиалам этой фирмы, находящимся в различных городах страны.
Каналы передачи информации в этой стране, как уже говорилось, контролируются государством, поэтому за передачу по ним информации приходится платить деньги. Ситуация также осложняется тем, что каналы однонаправленные, то есть информацию по ним можно передавать только в одном направлении.
Пусть, для удобства, города пронумерованы натуральными числами от 1 до n. Главный офис находится в городе номер 1, таким образом, необходимо найти такой набор каналов связи, по которым можно доставить файл от города номер 1 до любого другого, а среди всех таких наборов выбрать имеющий наименьшую суммарную стоимость.
Задан список каналов связи, которыми может воспользоваться фирма. Напишите программу, находящую требуемый набор каналов связи.
Входные данные
Первая строка входного файла INPUT.TXT содержит числа n и m - количество городов и количество каналов связи соответственно (1 ≤ n ≤ 22, 0 ≤ m ≤ 22). Последующие m содержат описания каналов связи. Каждое описание содержит три целых числа: u, v и c - соответственно номера городов, соединенных каналом и стоимость пересылки файла по этому каналу (1 ≤ u, v ≤ n, 0 ≤ c ≤ 1000). Ни один из каналов не соединяет город с самим собой, но между двумя городами может быть больше одного канала.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите стоимость пересылки файла и число каналов, обеспечивающих такую стоимость. Во второй строке выведите номера каналов, составляющих такой набор. Каналы нумеруются от 1 до m в том порядке, в котором они перечислены во входном файле.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 2
1 2 3
1 2 4 | 3 1
1 |
| 2 | 3 3
1 2 5
1 3 10
3 2 4 | 14 2
2 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
