Сейчас во всем мире в целях повышения безопасности вождения и уменьшения пробок вводится одностороннее движение. Правительство Берляндии решило не отставать от новой тенденции. Раньше в Берляндии все n городов были соединены n двусторонними дорогами в кольцо, т. е. каждый город был соединен напрямую ровно с двумя другими, и из каждого города можно было добраться до любого другого. Правительство Берляндии ввело одностороннее движение на всех n дорогах, но вскоре выяснилось, что из некоторых городов нельзя доехать до некоторых других. Сейчас для каждой дороги известно, в какую сторону направлено движение по ней, и стоимость перенаправления движения. Какую наименьшую сумму денег придется потратить правительству на переориентирование дорог так, чтобы из каждого города можно было добраться до любого другого?
В первой строке записано целое число n (3 ≤ n ≤ 100) — количество городов (и дорог) в Берляндии. Далее в n строках находятся описания дорог. Каждая дорога описывается тремя целыми числами ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) — дорога направлена из города ai в город bi, перенаправление движения стоит ci.
Выведите одно целое число — какую наименьшую сумму денег придется потратить правительству на перенаправление дорог так, чтобы из каждого города можно было добраться до любого другого по этим дорогам.
3 1 3 1 1 2 1 3 2 1
1
3 1 3 1 1 2 5 3 2 1
2
6 1 5 4 5 3 8 2 4 15 1 6 16 2 3 23 4 6 42
39
4 1 2 9 2 3 8 3 4 7 4 1 5
0
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач