Problem
Tanınmış bir ülkenin hükümeti, yol sistemini küresel olarak yeniden inşa etmeye karar verdi - ndash; şimdiden tüm yolları yok etmeyi başardı ve şimdi yol ağını yeniden inşa etmek gerekiyor. Herhangi iki şehir arasında yeni çift yönlü yollar inşa edilebilir ve yolun yapım maliyeti, ilgili şehirler arasındaki mesafeye eşittir. Ancak bazı durumlarda arazi, farklı bir fiyata yol inşa etmenize izin verir, bu tür şehir çiftlerine özel denir. Hükümet her şeyden önce bu ülkenin iki ana şehrini birbirine bağlamaya karar verdi – ndash; A ve B. Size, inşa edilen tüm yolların toplam maliyetinin mümkün olduğunca düşük olacağı ve aynı zamanda inşa edilen yollar boyunca, yolların inşası için bir plan geliştirmeniz talimatı verildi. A şehrinden B şehrine.
Girdi
İlk satır N sayısını içerir – ülkedeki şehir sayısı (
\(1\leq N\leq10^4\)). Aşağıdaki N satırın her biri iki tamsayı içerir, xi ve yi – karşılık gelen şehrin koordinatları (
\(|x|, |y| \leq 10^6\) ). Aşağıda M – özel şehir çiftlerinin sayısı (
\(0\leq M \leq min(10^4, N(N-1)/2)\). Sonraki M satırları her biri üç tamsayıdan oluşan özel yolların açıklamasını içerir: u, v - özel yolun geçtiği bir çift farklı şehir ve w - ilgili yolu inşa etme maliyeti (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)).Son satır, A ve B şehirlerinin numaralarını içerir (1'den N'ye).< br />
Künye
Bir sayı yazdır – istenen minimum uzunluk Yanıtınız doğru yanıttan en fazla 10
−5 farklı olmalıdır.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |