Caixeiro Viajante

Paulo é um caixeiro viajante, que visita clientes nas cidades do reino da Nlogônia para demonstrar novos produtos da empresa para a qual trabalha.

Paulo está organizando uma viagem para visitar cada uma das $N$ cidades do reino. A Nlogônia é imensa, as cidades são distantes, de forma que Paulo vai sempre usar transporte aéreo para ir de uma cidade a outra. Paulo conhece o tempo de voo entre cada par de cidades, mas não gosta de viajar de avião e quer minimizar o tempo de voo total para a viagem. No entanto, Paulo tem uma demanda peculiar quanto à ordem das cidades que vai visitar.

Na Nlogônia os “nomes” das cidades são números inteiros de $1$ a $N$. Paulo deseja que a ordem das cidades que vai visitar obedeçam à seguinte regra: quando Paulo visitar a cidade $K$, ou todas as cidades de nomes menores do que $K$ já foram visitadas ou todas serão visitadas após $K$. Por exemplo, se $N$ é igual a três, Paulo pode visitar as cidades nas ordens $1$, $2$, $3$ ou na ordem $3$, $2$, $1$ ou na ordem $2$, $1$, $3$, mas não pode visitá-las na ordem $1$, $3$, $2$, pois quando visita a cidade $3$, como $1$ já foi visitada, $2$ também deveria ter sido visitada.

Escreva um programa para determinar o tempo mínimo total de voo para a viagem de Paulo, iniciando em qualquer cidade, terminando em qualquer cidade, mas visitando cada cidade uma única vez.

Entrada

A primeira linha da entrada contém um inteiro $N$, o número de cidades. Cada uma das $N(N - 1)/2$ linhas contém três inteiros $A$, $B$ e $T$, indicando que o tempo de voo da cidade $A$ para a cidade $B$ é $T$ (o tempo de voo da cidade $B$ para a cidade $A$ também é $T$).

Saída

Seu programa deve produzir uma única linha, contendo um único número inteiro, o tempo mínimo total de voo para a viagem de Paulo.

Restrições

• $2 \leq N \leq 1\ 500$
• $1\leq A < B\leq N$
• $1 \leq T \leq 1\ 000$

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo $25$ pontos, $1 \leq N \leq 10$.
• Para um conjunto adicional de casos de testes valendo $50$ pontos, $1 \leq N \leq 20$.
• Para um conjunto adicional de casos de testes valendo $25$ pontos, nenhuma restrição adicional.

Exemplo de Entrada 1

3
1 2 5
1 3 2
2 3 4

Exemplo de Saída 1

7

Exemplo de Entrada 2

4
1 2 15
1 3 7
1 4 8
2 3 16
2 4 9
3 4 12

Exemplo de Saída 2

31