A. Кольцевая
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Сейчас во всем мире в целях повышения безопасности вождения и уменьшения пробок вводится одностороннее движение. Правительство Берляндии решило не отставать от новой тенденции. Раньше в Берляндии все 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