Problem
Chính phủ của một số quốc gia nổi tiếng đã quyết định xây dựng lại hệ thống đường bộ trên toàn cầu – nó đã phá hủy tất cả các con đường, và bây giờ cần phải xây dựng lại mạng lưới đường bộ. Những con đường hai chiều mới có thể được xây dựng giữa hai thành phố bất kỳ và chi phí để xây dựng con đường bằng với khoảng cách giữa các thành phố tương ứng. Tuy nhiên, trong một số trường hợp, địa hình cho phép bạn xây dựng một con đường với một mức giá khác, những cặp thành phố như vậy được gọi là đặc biệt. Trước hết, chính phủ quyết định kết nối hai thành phố chính của đất nước này – A và B. Bạn được hướng dẫn lập kế hoạch xây dựng đường, trong đó tổng chi phí của tất cả các con đường được xây dựng sẽ thấp nhất có thể, đồng thời, dọc theo các con đường đã xây dựng, có thể thu được từ thành phố A đến thành phố B.
Đầu vào
Dòng đầu tiên chứa số N – số thành phố trong cả nước (
\(1\leq N\leq10^4\)). Mỗi dòng trong số N dòng sau chứa hai số nguyên xi và yi – tọa độ của thành phố tương ứng (
\(|x|, |y| \leq 10^6\) ). Phần sau chứa số M – số cặp thành phố đặc biệt (
\(0\leq M \leq min(10^4, N(N-1)/2)\). M dòng tiếp theo chứa mô tả về những con đường đặc biệt, mỗi con đường bao gồm ba số nguyên: u, v – một cặp thành phố khác nhau mà con đường đặc biệt đi qua và w – chi phí xây dựng con đường tương ứng (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). Dòng cuối cùng chứa số thành phố A và B (từ 1 đến N).< br />
Dấu ấn
In một số – chiều dài tối thiểu mong muốn. Câu trả lời của bạn không được khác câu trả lời đúng quá 10
−5.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |