میانبر (AB)
Problem
شرحی از شبکه راه های کشور به شما داده می شود. وظیفه شما – طول کوتاه ترین مسیر بین شهرهای A و B را پیدا کنید.
ورودی
شبکه راه در فایل ورودی به صورت زیر آورده شده است: خط اول شامل اعداد N و K (1<=N<=100000، 0<=K<=300000)، که در آن K – تعداد جاده ها هر یک از خطوط K زیر حاوی توضیحاتی از یک جاده دو طرفه است – سه عدد صحیح ai، bi و li (1aibiN، 1li106). به این معنی که جاده ای به طول لی وجود دارد که از شهر آی به شهر بی منتهی می شود. خط آخر شامل دو عدد A و B – تعداد شهرهایی که لازم است کمترین فاصله بین آنها محاسبه شود (1<=A,B<=N )
حصر
شما باید شماره واحد – فاصله بین شهرهای مورد نیاز اگر دسترسی از شهر A به شهر B از طریق جاده غیرممکن است، چاپ –1.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |