Le follie dell’imperatore

Durante il 1800 l’imperatore del Giappone vietò ai contadini di effettuare il percorso più breve dal palazzo ai giardini imperiali, chiamato Via dell’Illuminazione.

Più precisamente la legge imponeva ai contadini di intraprendere percorsi più lunghi della Via dell’Illuminazione per arrivare dal palazzo ai giardini imperiali, senza impedirgli di percorrere parti della Via dell’Illuminazione.
Ciascun tratto dei percorsi era a senso unico e si snodava anche attraverso ponti e gallerie sotterranee.
Inoltre, la rete stradale era tale che seguendo i sensi unici era impossibile passare due volte per lo stesso luogo.

Il vostro compito è quello di aiutare i contadini a calcolare la lunghezza del percorso minimo che non sia vietato dall’imperatore e che vada dal palazzo ai giardini imperiali.

Dati in Input

Il file input.txt elenca le strade che portano dal palazzo ai giardini.
Nella prima riga sono presenti due numeri: il numero N di incroci ed il numero M di collegamenti fra gli stessi.

Seguono quindi M righe che descrivono M strade; in ogni riga viene indicato l’indice X dell’incrocio di entrata, l’indice Y dell’incrocio di uscita e la lunghezza W della strada.

Il palazzo è situato nell’incrocio 1, i giardini nell’incrocio M.

Dati in Output

Il file output.txt contiene un unico intero: la lunghezza di uno dei secondi percorsi più brevi.

Assunzioni

  • 3 ≤ N ≤ 2000
  • 1 ≤ M ≤ 80000
  • 1 ≤ X, Y ≤ N
  • 1 ≤ W ≤ 10000
  • Il programma deve terminare entro 3 secondi.

Esempi

input.txt output.txt
1 4 4
1 2 1
2 3 1
2 4 4
3 4 1
5
2 4 5
1 2 1
1 3 2
1 4 4
2 4 2
3 4 1
4