Компания MST (Meaningless State Team) выиграла очередной тендер на проведение важной государственной реформы в Берляндии.
В Берляндии n городов, некоторые пары из которых соединены дорогами. У каждой дороги есть ее стоимость. По любой дороге можно двигаться в любом направлении. Компания MST должна провести ремонтные работы на некотором таком наборе дорог, что из любого города можно добраться до любого другого, двигаясь только по отремонтированным дорогам. Кроме того, этот набор должен содержать ровно k столичных дорог (то есть таких, что одним из ее концов является столица). Столица имеет номер 1.
Так как бюджет работ уже утвержден, то компании MST выгодно найти такой набор, что сумма длин входящих в него дорог наименьшая.
Выходные данные
Выведите количество дорог в искомом наборе в первую строку. Вторая строка должна содержать номера дорог, включенных в искомое множество. Если искомого набора не существует, то выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 2
1 2 1
2 3 1
3 4 1
1 3 3
1 4 2
|
3
1 5 2
|