Caixeiro Viajante - A revolta

Mathias é um mercador muito habilidoso em negociações pela internet, e no final de cada mês, ele planeja um caminho para realizar as suas entregas entre diversas cidades. Mathias também é um membro ativo da comunidade de Caixeiros Viajantes, no qual recebe mensalmente atualizações no seu dispositivo para mapear o caminho de suas entregas.

Porém, um dia, Mathias percebeu que era possível encontrar um caminho mais rápdio que passasse por todas as cidades do que o caminho indicado pelo dispositivo. Mathias ficou em choque, e, ao mesmo tempo, revoltado com a situação, pois percebeu que toda a comunidade era uma farsa para que a elite dos caixeiros viajantes pudessem realizar as entregas mais rápidas.

Para encontrar esse caminho mais rápido, Mathias percebeu que poderia passar mais de uma vez por uma mesma cidade, o que poderia encurtar o trajeto, conforme exemplo abaixo:

4 cidades
Os percursos disponíveis e o respectivo tempo:
A -> B = 5
A -> C = 5
A -> D = 8
B -> A = 10
B -> C = 7
B -> D = 1
C -> A = 8
C -> B = 15
C -> D = 9
D -> A = 1
D -> B = 14
D -> C = 7

Rota fornecida pelo dispositivo:

A->B->D->C
5 + 1 + 7 = 13

Rota de menor tempo:

A->B->D->A->C
5 + 1 + 1 + 5 = 12

• Note que tempo de A->B pode ser diferente de B->A.

Mathias sempre sai de sua cidade, com uma van alugada, e distribui seus produtos até a última cidade, no qual deixa sua van e volta para sua cidade de avião por conta do conforto e tempo. Como a maioria do tempo de demora das entregas é exclusivamente devido ao transporte, ele quer desenvolver um algoritmo independente que escancare a farsa da comunidade dos Caixeiros Viajantes e o faça realizar suas entregas em menor tempo que seus concorrentes.

Será fornecido na primeira linha um $N$ representando a quantidade de paradas. $(1 \lt N \le 22)$

Nas próximas $N$ linhas $i$ serão fornecidos $N$ valores $j$ representando o tempo para percorrer da parada $i$ até a parada $j$, representando a matriz de adjacência.

A cidade de Mathias é sempre a primeira.

Deverá ser dado como saida o menor tempo no qual Mathias consegue realizar o percurso até a última cidade.