Module: خوارزمية ديكسترا

Problem

قررت حكومة بعض البلدان المعروفة إعادة بناء نظام الطرق على مستوى العالم - لقد نجحت بالفعل في تدمير جميع الطرق ، والآن من الضروري إعادة بناء شبكة الطرق. يمكن بناء طرق جديدة ذات اتجاهين بين أي مدينتين ، وتكلفة بناء الطريق تساوي المسافة بين المدن المعنية. ومع ذلك ، في بعض الحالات ، تسمح لك التضاريس ببناء طريق بسعر مختلف ، ويطلق على أزواج المدن هذه اسم خاص. قررت الحكومة أولاً وقبل كل شيء ربط المدينتين الرئيسيتين في هذا البلد - أ و ب. لقد تم توجيهك لوضع خطة لبناء الطرق ، حيث ستكون التكلفة الإجمالية لجميع الطرق المشيدة منخفضة قدر الإمكان ، وفي نفس الوقت ، على طول الطرق المشيدة ، سيكون من الممكن الحصول عليها من مدينة أ الى مدينة ب.

إدخال
يحتوي السطر الأول على الرقم N & ndash؛ عدد المدن في البلد ( \ (1 \ leq N \ leq10 ^ 4 \) ). يحتوي كل سطر من الأسطر N التالية على عددين صحيحين ، xi و yi & ndash؛ إحداثيات المدينة المطابقة ( \ (| x | ، | y | \ leq 10 ^ 6 \) & nbsp؛). التالي يحتوي على الرقم M & ndash؛ عدد الأزواج الخاصة من المدن ( \ (0 \ leq M \ leq min (10 ^ 4، N (N-1) / 2) \) . التالي M خطوط تحتوي على وصف للطرق الخاصة ، كل منها يتكون من ثلاثة أعداد صحيحة: u ، v & ndash ؛ زوج من المدن المختلفة التي يمر بينها الطريق الخاص ، و & ndash ؛ تكلفة بناء الطريق المقابل ( \ (1 \ leq u، v \ leq N، 0 \ leq w \ leq 10 ^ 6 \) ). يحتوي السطر الأخير على أرقام المدن A و B (من 1 إلى N). < ر />
بصمة
طباعة رقم واحد & ndash؛ الطول المطلوب. يجب أن تختلف إجابتك عن الإجابة الصحيحة بما لا يزيد عن 10 ^{& minus؛ 5} .

أمثلة <الجسم>

#	إدخال	الإخراج
1	4 1 1 0 0 10 0 1 1 1 2100 2 1	2.0000000000