هموار کردن راه
Problem
دولت یکی از کشورهای معروف تصمیم به بازسازی جهانی سیستم جاده ای گرفت – قبلاً توانسته است تمام جاده ها را ویران کند و اکنون باید شبکه راه ها را بازسازی کرد. جاده های دو طرفه جدید را می توان بین هر دو شهر ساخت و هزینه ساخت جاده برابر با فاصله بین شهرهای مربوطه است. با این حال، در برخی موارد، زمین به شما امکان می دهد جاده ای را با قیمت متفاوت بسازید، چنین جفت شهرها ویژه نامیده می شوند. دولت قبل از هر چیز تصمیم گرفت دو شهر اصلی این کشور را به هم متصل کند – الف و ب. به شما دستور داده شد که طرحی برای ساخت جاده ها تهیه کنید که در آن هزینه کل تمام راه های ساخته شده تا حد امکان پایین باشد و در عین حال در امتداد جاده های ساخته شده امکان دریافت از شهر 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 &ndash؛ یک جفت شهر مختلف که جاده ویژه از بین آنها می گذرد و 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 |