Les vaches détestent la gymnastique (les exercices), mais aiment un peu le jogging. Elles ont étudié leur pâturage et listé tous les chemins possibles. Ceux-ci sont « orientés » : on ne peut les parcourir que dans un sens. Parfois deux chemins différents relient une paire de points, dans des sens opposés.

Aidez-les à trouver le plus court « circuit » pour courir. Un circuit commence et finit au même endroit. Sa longueur est la somme des longueurs des chemins parcourus pour en faire le tour.

Les chemins relient deux points, nommés par des entiers positifs et numérotés consécutivement dès 1. Les distances sont des entiers positifs.

Tout pâturage fourni contient au moins un circuit.

Entrée

• Ligne $1$ : $N$ ($1 \le N \le 2000$), nombre de chemins orientés ; au plus 400 points distincts.
• Lignes $2..N+1$ : début, fin et distance (au plus 1000) d’un chemin.

Sortie

Une ligne avec la distance entière du plus court circuit possible.

Exemples

Entrée 1

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

Sortie 1

12

Auteurs : Hal Burch et Russ Cox