रास्ता बनाओ
Problem
कुछ प्रसिद्ध देश की सरकार ने विश्व स्तर पर सड़क व्यवस्था के पुनर्निर्माण का निर्णय लिया - यह पहले ही सभी सड़कों को नष्ट करने में कामयाब हो चुका है, और अब सड़क नेटवर्क का पुनर्निर्माण करना आवश्यक है। किन्हीं भी दो शहरों के बीच नई दो-तरफ़ा सड़कें बनाई जा सकती हैं, और सड़क बनाने की लागत संबंधित शहरों के बीच की दूरी के बराबर होती है। हालाँकि, कुछ मामलों में, इलाके आपको एक अलग कीमत के लिए सड़क बनाने की अनुमति देते हैं, ऐसे शहरों के जोड़े को विशेष कहा जाता है। सरकार ने सबसे पहले इस देश के दो मुख्य शहरों को जोड़ने का फैसला किया- ए और बी। आपको सड़कों के निर्माण के लिए एक योजना विकसित करने का निर्देश दिया गया था, जिसमें सभी निर्मित सड़कों की कुल लागत यथासंभव कम होगी, और साथ ही, निर्मित सड़कों के साथ-साथ, प्राप्त करना संभव होगा। शहर ए से शहर बी तक।
इनपुट
पहली पंक्ति में संख्या N – देश में शहरों की संख्या (\(1\leq N\leq10^4\))। निम्नलिखित एन लाइनों में से प्रत्येक में दो पूर्णांक, xi और y - होते हैं; संबंधित शहर के निर्देशांक (\(|x|, |y| \leq 10^6\) )। निम्नलिखित में संख्या M – शहरों के विशेष जोड़े की संख्या (\(0\leq M \leq min(10^4, N(N-1)/2)\)। अगली M लाइनें विशेष सड़कों का विवरण होता है, जिनमें से प्रत्येक में तीन पूर्णांक होते हैं: यू, वी - विभिन्न शहरों की एक जोड़ी जिसके बीच विशेष सड़क गुजरती है, और डब्ल्यू - इसी सड़क के निर्माण की लागत (\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\))। अंतिम पंक्ति में शहरों A और B की संख्या है (1 से N तक)।< बीआर />
छाप
एक नंबर प्रिंट करें – वांछित न्यूनतम लंबाई। आपका उत्तर सही उत्तर से 10−5 से अधिक भिन्न नहीं होना चाहिए।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |