Problem
Anda diberi penerangan tentang rangkaian jalan raya negara. Tugas anda – cari panjang laluan terpendek antara bandar A dan B.
Input
Rangkaian jalan diberikan dalam fail input seperti berikut: baris pertama mengandungi nombor N dan K (1<=N<=100000, 0<=K<=300000), di mana K – bilangan jalan. Setiap baris K berikut mengandungi penerangan tentang jalan dua hala – tiga integer ai, bi dan li (1aibiN, 1li106). Ini bermakna terdapat jalan sepanjang li yang menghala dari bandar ai ke bandar bi. Baris terakhir mengandungi dua nombor A dan B – bilangan bandar di antaranya adalah perlu untuk mengira jarak terpendek (1<=A,B<=N )
Cetakan
Anda mesti mengeluarkan nombor tunggal – jarak antara bandar yang diperlukan. Jika mustahil untuk pergi dari bandar A ke bandar B melalui jalan raya, cetak –1.
Contoh
| # |
Input |
Output |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |