Mach den Weg frei
Problem
Die Regierung eines bekannten Landes hat beschlossen, das Straßensystem global neu zu bauen; Es hat bereits alle Straßen zerstört, und jetzt muss das Straßennetz neu aufgebaut werden. Zwischen zwei beliebigen Städten können neue bilaterale Straßen gebaut werden, und die Kosten für den Bau einer Straße entsprechen der Entfernung zwischen den jeweiligen Städten. In einigen Fällen erlaubt die Landschaft jedoch, eine Straße für einen anderen Preis zu bauen, solche Paare von Städten werden als besonders bezeichnet. Die Regierung hat als erstes beschlossen, die beiden wichtigsten Städte des Landes zu verbinden, A und B. Sie wurden beauftragt, einen Straßenplan zu erstellen, bei dem die Gesamtkosten aller gebauten Straßen möglichst gering sind und die gebauten Straßen von Stadt A nach Stadt B gelangen können.
Eingabe
Die erste Zeile enthält die Zahl N – Anzahl der Städte im Land (
\(1\leq N\leq10^4\)). Jede der folgenden N Zeilen enthält zwei ganze Zahlen, xi und yi – die Koordinaten der entsprechenden Stadt (
\(|x|, |y| \leq 10^6\) ). Im Folgenden finden Sie die Anzahl M – die Anzahl der speziellen Stadtpaare (
\(0\leq M \leq min(10^4, N(N-1)/2)\). Die folgenden Zeilen enthalten eine Beschreibung der besonderen Straßen, die jeweils aus drei ganzen Zahlen bestehen: u, v – ein Paar verschiedener Städte, zwischen denen eine besondere Straße verläuft, und w – die Kosten für den Bau der entsprechenden Straße (\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). Die letzte Zeile enthält die Nummern der Städte A und B (1 bis N).
Ausgabe
Geben Sie eine Zahl aus, um die gewünschte Mindestlänge zu finden. Ihre Antwort sollte nicht mehr als 10−5 von der richtigen Antwort abweichen.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
4
1 1
0 0
1 0
0 1
1
1 2 100
2 1 |
2.0000000000 |