Scorciatoia (AB)
Problem
Ti viene fornita una descrizione della rete stradale del paese. Il tuo compito – trova la lunghezza del percorso più breve tra le città A e B.
Inserimento
La rete stradale è data nel file di input come segue: la prima riga contiene i numeri N e K (1<=N<=100000, 0<=K<=300000), dove K – numero di strade. Ognuna delle seguenti righe K contiene una descrizione di una strada a doppio senso – tre numeri interi ai, bi e li (1aibiN, 1li106). Ciò significa che esiste una strada di lunghezza li che porta dalla città ai alla città bi. L'ultima riga contiene due numeri A e B – numeri di città tra le quali è necessario calcolare la distanza più breve (1<=A,B<=N )
Impressum
Devi emettere il singolo numero – distanza tra le città richieste. Se è impossibile andare dalla città A alla città B su strada, stampa –1.
Esempi
| # |
Input |
Uscita |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |