Problem
Bạn được cung cấp một mô tả về mạng lưới đường bộ của đất nước. Nhiệm vụ của bạn – tìm độ dài của con đường ngắn nhất giữa các thành phố A và B.
Đầu vào
Mạng đường được cung cấp trong tệp đầu vào như sau: dòng đầu tiên chứa các số N và K (1<=N<=100000, 0<=K<=300000), trong đó K – số đường. Mỗi dòng trong số K dòng sau chứa mô tả về đường hai chiều – ba số nguyên ai, bi, li (1aibiN, 1li106). Điều này có nghĩa là có một con đường dài li dẫn từ thành phố ai đến thành phố bi. Dòng cuối cùng chứa hai số A và B – số lượng thành phố cần tính khoảng cách ngắn nhất giữa chúng (1<=A,B<=N )
Dấu ấn
Bạn phải xuất một số duy nhất – khoảng cách giữa các thành phố cần thiết. Nếu không thể đi từ thành phố A đến thành phố B bằng đường bộ, hãy in –1.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |