Problem
국가의 도로망에 대한 설명이 제공됩니다. 귀하의 작업 – 도시 A와 B 사이의 최단 경로 길이를 찾으십시오.
입력
도로 네트워크는 다음과 같이 입력 파일에 제공됩니다. 첫 번째 줄에는 숫자 N과 K(1<=N<=100000, 0<=K<=300000)가 포함됩니다. 도로의 수. 다음의 각 K 행에는 양방향 도로에 대한 설명이 포함되어 있습니다. 3개의 정수 ai, bi 및 li(1aibiN, 1li106). 이것은 도시 ai에서 도시 bi로 이어지는 길이 li의 도로가 있음을 의미합니다. 마지막 줄에는 두 개의 숫자 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 |