Module: Dijkstra's algorithm


Problem

11 /14


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