Задача O. Водопроводная сеть ≡

Условие

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

В качестве входных данных им выдали карту, представленную в виде взвешенного графа, вершины которого отвечают за населенные пункты (с расположенными в них распределительными станциями), а ребра обозначают соединяющие их магистрали. Каждое ребро имеет вес, указывающий длину соответствующей магистрали.

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

В целях экономии ресурсов также необходимо чтобы такая сеть имела минимально возможную длину.

При решении задачи следует полагать, что в полученной сети существует всего лишь один источник воды, от которого будут запитываться все остальные узлы.

Формат входного файла

В начале входного файла "input.txt" записаны два натуральных числа: n — число вершин и m — число соединяющих их ребер. Далее следует набор из m таких ребер, каждое из которых представлено тройкой целых чисел: (a_i, b_i) — номера вершин, w_i — вес ребра. При этом полагается, что нумерация вершин начинается с нуля.

Формат выходного файла

В выходной файл "output.txt" следует вывести номера тех ребер, через которые должен пройти водопровод. При этом полагается, что нумерация ребер начинается с нуля.

Ограничения

Гарантируется, что исходный граф является связным, т.е. между любой парой его вершин можно проложить маршрут.

2 ≤ n ≤ 1000, 1 ≤ m ≤ (n ⋅ (n − 1)) / 2,

0 ≤ (a_i, b_i) < n, 0 < w_i ≤ 10

Примеры тестов

4
5
0 3 1
0 1 2
1 2 1
3 1 1
2 3 1

0
2
3

4
5
1 2 1
0 2 2
2 3 1
3 0 3
3 1 1

0
1
2