В одном королевстве имеется n городов и m двусторонних дорог. Каждая дорога соединяет пару городов, причём для каждой дороги известен уровень недовольства ею автомобилистами — величина wi.
Для каждой дороги известна величина ci — сколько надо потратить лямзиков, чтобы уменьшить уровень недовольства этой дорогой на единицу. Таким образом, чтобы уменьшить недовольство i-й дорогой на k, надо потратить k·ci лямзиков. При этом допустимо, чтобы недовольство стало нулевым или даже отрицательным.
В соответствии с приказом короля, необходимо выбрать n - 1 дорогу, сделав их главными дорогами. Должно выполняться важное условие: из любого города должно быть возможно проехать в любой другой по главным дорогам.
У министерства дорог есть бюджет S лямзиков на проведение реформы. Министерство планирует потратить этот бюджет на ремонт некоторых дорог (то есть уменьшить недовольство ими), а уже затем выбрать n - 1 главную дорогу.
Помогите потратить бюджет так, а затем и произвести выбор главных дорог, чтобы суммарное недовольство главными дорогами было как можно меньше. При этом величина недовольства некоторыми дорогами может стать отрицательной. Не обязательно тратить весь бюджет S полностью.
Гарантируется, что из любого города королевства можно добраться по дорогам в любой другой город королевства. Каждая дорога в королевстве — двусторонняя.
Выходные данные
В первой строке выведите K — минимально возможное суммарное недовольство главными дорогами.
В следующих n - 1 строках выведите по два целых числа x, vx — означающих, что дорога x является главной, и дорога x после реформы имеет уровень недовольства vx.
Считайте, что дороги пронумерованы от 1 до m в порядке их задания во входных данных. Номера рёбер можно выводить в произвольном порядке. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 9
1 3 1 1 3 1 2 2 2
4 1 4 2 2 5 3 1 6
1 2
1 3
2 3
2 4
2 5
3 5
3 6
4 5
5 6
7
|
0
1 1
3 1
6 1
7 2
8 -5
|
|
2
|
3 3
9 5 1
7 7 2
2 1
3 1
3 2
2
|
5
3 0
2 5
|