Коровы ненавидят гимнастику (упражнения), но немного любят бег трусцой. Они изучили пастбище и составили список всех возможных дорожек. Дорожки «направленные»: их можно проходить лишь в одну сторону. Иногда два разных пути связывают пару точек в противоположных направлениях.

Помогите найти кратчайший «круговой маршрут» для бега. Он начинается и заканчивается в одном месте. Длина — сумма длин дорожек, проходимых при обходе.

Дорожки соединяют две точки. Точки названы положительными целыми, последовательно начиная с 1. Расстояния — положительные целые.

Гарантируется хотя бы один круговой маршрут в каждом заданном пастбище.

Входные данные

• Строка $1$: $N$ ($1 \le N \le 2000$), число направленных дорожек; различных точек не более 400.
• Строки $2..N+1$: начало, конец и расстояние (не более 1000) одной дорожки.

Выходные данные

Одна строка с целой длиной кратчайшего возможного круга.

Примеры

Входные данные 1

4
3 1 5
1 2 4
2 3 3
1 3 44

Выходные данные 1

12

Авторы задачи: Hal Burch и Russ Cox