Задача №111818. Сортировка рёбер по длине
Ориентированный взвешенный граф задан перечнем дуг (ориентированных рёбер). Отсортировать эти дуги по возрастанию длин, сохранив (в дополнительных полях) номера этих дуг во входных данных.
Первая строка содержит количество вершин N ( 2 ≤ N ≤ 30000 ) и количество дуг (ориентированных рёбер) M ( 1 ≤ M ≤ 123456 ). Каждая из последующих M строк содержит ровно три целых числа u , v и len — начало, конец и длину дуги. 1 ≤ u , v ≤ N , u ≠ v , 1 ≤ len ≤ 10 9 . Гарантированно, что дл и ны всех дуг различны.
Результат должен содержать M строк по четыре целых числа u , v , len , idx в каждой — начало, конец, длину дуг и , и её номер во входных данных (нумерация с единицы). При этом д у ги должны быть отсортированы по возрастанию длин.
3 4 3 2 4 3 1 8 1 2 14 1 3 2
1 3 2 4 3 2 4 1 3 1 8 2 1 2 14 3