E. Компания MST
ограничение по времени на тест
8 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Компания MST (Meaningless State Team) выиграла очередной тендер на проведение важной государственной реформы в Берляндии.

В Берляндии n городов, некоторые пары из которых соединены дорогами. У каждой дороги есть ее стоимость. По любой дороге можно двигаться в любом направлении. Компания MST должна провести ремонтные работы на некотором таком наборе дорог, что из любого города можно добраться до любого другого, двигаясь только по отремонтированным дорогам. Кроме того, этот набор должен содержать ровно k столичных дорог (то есть таких, что одним из ее концов является столица). Столица имеет номер 1.

Так как бюджет работ уже утвержден, то компании MST выгодно найти такой набор, что сумма длин входящих в него дорог наименьшая.

Входные данные

Первая строка входного файла содержит три целых числа n, m, k (1 ≤ n ≤ 5000;0 ≤ m ≤ 105;0 ≤ k < 5000), где n — это количество городов в стране, m — количество дорог в стране, k — количество столичных дорог в искомом наборе. Далее в m строках перечислены сами дороги. Каждая дорога задана тройкой чисел ai, bi, wi (1 ≤ ai, bi ≤ n; 1 ≤ w ≤ 105), где ai, bi — это номера городов, соединяемых дорогой, а wi — это ее длина.

Между каждой парой городов существует не более одной дороги. Нет дорог, ведущих из себя в себя же. Столица имеет номер 1.

Выходные данные

Выведите количество дорог в искомом наборе в первую строку. Вторая строка должна содержать номера дорог, включенных в искомое множество. Если искомого набора не существует, то выведите -1.

Примеры
Входные данные
4 5 2
1 2 1
2 3 1
3 4 1
1 3 3
1 4 2
Выходные данные
3
1 5 2