Problem
Kerajaan beberapa negara terkenal memutuskan untuk membina semula sistem jalan raya secara global – ia telah berjaya memusnahkan semua jalan raya, dan kini adalah perlu untuk membina semula rangkaian jalan raya. Jalan dua hala baharu boleh dibina antara mana-mana dua bandar, dan kos untuk membina jalan itu adalah sama dengan jarak antara bandar masing-masing. Walau bagaimanapun, dalam beberapa kes, rupa bumi membolehkan anda membina jalan dengan harga yang berbeza, pasangan bandar sedemikian dipanggil istimewa. Kerajaan memutuskan pertama sekali untuk menghubungkan dua bandar utama negara ini – A dan B. Anda telah diarahkan untuk membangunkan rancangan untuk pembinaan jalan raya, di mana jumlah kos semua jalan yang dibina adalah serendah mungkin, dan pada masa yang sama, di sepanjang jalan yang dibina, adalah mungkin untuk mendapatkan dari bandar A ke bandar B.
Input
Baris pertama mengandungi nombor N – bilangan bandar di negara ini (
\(1\leq N\leq10^4\)). Setiap baris N berikut mengandungi dua integer, xi dan yi – koordinat bandar yang sepadan (
\(|x|, |y| \leq 10^6\) ). Yang berikut mengandungi nombor M – bilangan pasangan bandar istimewa (
\(0\leq M \leq min(10^4, N(N-1)/2)\). Baris M seterusnya mengandungi perihalan jalan khas, setiap satunya terdiri daripada tiga integer: u, v – sepasang bandar berbeza antara yang dilalui jalan khas dan w – kos membina jalan yang sepadan (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). Baris terakhir mengandungi nombor bandar A dan B (dari 1 hingga N).< br />
Cetakan
Cetak satu nombor – panjang minimum yang dikehendaki. Jawapan anda hendaklah berbeza daripada yang betul tidak lebih daripada 10
&tolak;5.
Contoh
| # |
Input |
Output |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |