As vacas detestam ginástica (exercícios), mas gostam um pouco de correr. Examinaram o pasto e listaram todos os caminhos possíveis. São «dirigidos»: só se percorrem num sentido. Às vezes dois caminhos distintos ligam um par de pontos em sentidos opostos.

Ajude-as a encontrar a «rota circular» mais curta para correr. Começa e termina no mesmo local. O comprimento é a soma dos comprimentos dos caminhos percorridos numa volta.

Os caminhos ligam dois pontos, identificados por inteiros positivos consecutivos desde 1. As distâncias são inteiros positivos.

É garantida pelo menos uma rota circular em cada pasto fornecido.

Entrada

• Linha $1$: $N$ ($1 \le N \le 2000$), número de caminhos dirigidos; no máximo 400 pontos distintos.
• Linhas $2..N+1$: início, fim e distância (no máximo 1000) de um caminho.

Saída

Uma linha com a distância inteira do circuito mais curto possível.

Exemplos

Entrada 1

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

Saída 1

12

Autores: Hal Burch e Russ Cox