Le mucche odiano la ginnastica (esercizi), ma amano un po’ correre. Hanno esaminato il pascolo e listato tutti i sentieri possibili. Sono «diretti»: percorribili in un solo verso. Talvolta due sentieri diversi collegano due punti in versi opposti.

Trovate il «percorso circolare» più corto per correre. Inizia e finisce nello stesso luogo. La lunghezza è la somma delle lunghezze dei sentieri percorsi per il giro.

I sentieri collegano due punti, denominati interi positivi consecutivi a partire da 1. Le distanze sono interi positivi.

Ogni pascolo dato contiene almeno un percorso circolare.

Input

• Riga $1$: $N$ ($1 \le N \le 2000$), numero di sentieri diretti; al massimo 400 punti distinti.
• Righe $2..N+1$: inizio, fine e distanza (al massimo 1000) di un sentiero.

Output

Una riga con la distanza intera del circuito più corto possibile.

Esempi

Input 1

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

Output 1

12

Autori: Hal Burch e Russ Cox