The government of some well-known country decided to globally rebuild the road system – it has already managed to destroy all the roads, and now it is necessary to rebuild the road network. New two-way roads can be built between any two cities, and the cost to build the road is equal to the distance between the respective cities. However, in some cases, the terrain allows you to build a road for a different price, such pairs of cities are called special. The government decided first of all to connect the two main cities of this country – A and B. You were instructed to develop a plan for the construction of roads, in which the total cost of all constructed roads will be as low as possible, and at the same time, along the constructed roads, it will be possible to get from city A to city B.
Input
The first line contains the number N – number of cities in the country (
\(1\leq N\leq10^4\)). Each of the following N lines contains two integers, xi and yi – coordinates of the corresponding city (
\(|x|, |y| \leq 10^6\) ). The following contains the number M – number of special pairs of cities (
\(0\leq M \leq min(10^4, N(N-1)/2)\). Next M lines contain a description of special roads, each consisting of three integers: u, v – a pair of different cities between which the special road passes, and w – the cost of building the corresponding road (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)).The last line contains the numbers of cities A and B (from 1 to N).
Imprint
Print one number – desired minimum length. Your answer should differ from the correct one by no more than 10
−5.
Examples
| # |
Input |
Output |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |