Орієнтований зважений граф заданий переліком дуг (орієнтованих ребер). Відсортувати ці дуги за зростанням довжин, зберігши (додатковими полями) номери цих дуг у вхідних даних.

Вхідні дані

Перший рядок містить кількість вершин ~N~ (~2\leqslant N\leqslant 30000~) і кількість дуг (орієнтованих ребер) ~M~ (~1\leqslant M\leqslant 123456~). Кожен із подальших ~M~ рядків містить рівно три цілих числа ~u~, ~v~ та ~len~ – початок, кінець та довжину дуги. ~1\leqslant u, v\leqslant N~, ~u\neq v~, ~1\leqslant len\leqslant 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

Примітки

Задачу рекомендується розв'язати шляхом використання стандартного сортування та задання власного компаратора.