Problem
잘 알려진 일부 국가의 정부는 전 세계적으로 도로 시스템을 재건하기로 결정했습니다. 이미 모든 도로를 파괴했으며 이제 도로망을 재건해야 합니다. 새로운 양방향 도로는 두 도시 사이에 건설할 수 있으며 도로 건설 비용은 각 도시 간의 거리와 동일합니다. 그러나 경우에 따라 지형을 통해 다른 가격으로 도로를 건설할 수 있으며 이러한 도시 쌍을 특별이라고 합니다. 정부는 우선 이 나라의 두 주요 도시를 연결하기로 결정했습니다. A와 B. 건설된 모든 도로의 총 비용이 가능한 한 낮고 동시에 건설된 도로를 따라 다음을 얻을 수 있는 도로 건설 계획을 개발하라는 지시를 받았습니다. 도시 A에서 도시 B로.
입력
첫 번째 줄에는 숫자 N – 국가의 도시 수(
\(1\leq N\leq10^4\)). 다음 N 줄 각각에는 두 개의 정수 xi와 yi가 포함되어 있습니다. 해당 도시의 좌표(
\(|x|, |y| \leq 10^6\) ). 다음은 숫자 M – 도시의 특수 쌍 수(
\(0\leq M \leq min(10^4, N(N-1)/2)\). 다음 M 라인 u, v – 특수 도로가 통과하는 한 쌍의 다른 도시, w – 해당 도로 건설 비용(
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). 마지막 줄에는 도시 A와 B의 숫자가 포함됩니다(1에서 N까지).< br />
출판물
하나의 숫자 인쇄 – 원하는 최소 길이. 답은 정답과 10
±5 이상 차이가 나지 않아야 합니다.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |