Сейчас во всем мире в целях повышения безопасности вождения и уменьшения пробок вводится одностороннее движение. Правительство Берляндии решило не отставать от новой тенденции. Раньше в Берляндии все n городов были соединены n двусторонними дорогами в кольцо, т. е. каждый город был соединен напрямую ровно с двумя другими, и из каждого города можно было добраться до любого другого. Правительство Берляндии ввело одностороннее движение на всех n дорогах, но вскоре выяснилось, что из некоторых городов нельзя доехать до некоторых других. Сейчас для каждой дороги известно, в какую сторону направлено движение по ней, и стоимость перенаправления движения. Какую наименьшую сумму денег придется потратить правительству на переориентирование дорог так, чтобы из каждого города можно было добраться до любого другого?
Выходные данные
Выведите одно целое число — какую наименьшую сумму денег придется потратить правительству на перенаправление дорог так, чтобы из каждого города можно было добраться до любого другого по этим дорогам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3 1
1 2 1
3 2 1
|
1
|
|
2
|
3
1 3 1
1 2 5
3 2 1
|
2
|
|
3
|
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42
|
39
|
|
4
|
4
1 2 9
2 3 8
3 4 7
4 1 5
|
0
|