Shortcut (AB)
Problem
You are given a description of the country's road network. Your task – find the length of the shortest path between cities A and B.
Input
The road network is given in the input file as follows: the first line contains the numbers N and K (1<=N<=100000, 0<=K<=300000), where K – number of roads. Each of the following K lines contains a description of a two-way road – three integers ai, bi and li (1aibiN, 1li106). This means that there is a road of length li that leads from city ai to city bi. The last line contains two numbers A and B – numbers of cities between which it is necessary to calculate the shortest distance (1<=A,B<=N )
Imprint
You must output the single number – distance between required cities. If it is impossible to get from city A to city B by road, print –1.
Examples
| # |
Input |
Output |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |