Il secondo percorso più breve

Sono date n città e m strade bidirezionali che le collegano. Ogni strada ha una lunghezza corrispondente . Emil, un viaggiatore avventuroso, vuole andare dalla città 1 alla città n percorrendo queste strade. Tuttavia, ha in mente una variante particolare: cercherà il percorso più breve tra quelli che sono strettamente più lunghi rispetto al tragitto minimo complessivo.

In altre parole, il tuo compito è aiutare Emil a determinare la lunghezza del secondo percorso più breve dalla città 1 alla città n.

Input

La prima riga dell’input contiene due interi n e m, che rappresentano rispettivamente il numero di città e il numero di strade.
Le successive m righe contengono tre interi , e , i quali indicano che esiste una strada bidirezionale tra le città e , con lunghezza .

Output

Stampa un singolo intero che rappresenti la lunghezza del secondo percorso più breve dalla città 1 alla città n.

Esempi