Problem
El gobierno de algún conocido país decidió reconstruir globalmente el sistema vial – ya ha logrado destruir todas las carreteras, y ahora es necesario reconstruir la red de carreteras. Se pueden construir nuevas carreteras de doble sentido entre dos ciudades, y el costo de construir la carretera es igual a la distancia entre las ciudades respectivas. Sin embargo, en algunos casos, el terreno te permite construir un camino por un precio diferente, tales pares de ciudades se llaman especiales. El gobierno decidió en primer lugar conectar las dos principales ciudades de este país – A y B. Se le indicó que desarrollara un plan para la construcción de caminos, en el que el costo total de todos los caminos construidos sea lo más bajo posible y, al mismo tiempo, a lo largo de los caminos construidos, será posible obtener de la ciudad A a la ciudad B.
Entrada
La primera línea contiene el número N – número de ciudades del país (
\(1\leq N\leq10^4\)). Cada una de las N líneas siguientes contiene dos números enteros, xi y yi – coordenadas de la ciudad correspondiente (
\(|x|, |y| \leq 10^6\) ). Lo siguiente contiene el número M – número de pares especiales de ciudades (
\(0\leq M \leq min(10^4, N(N-1)/2)\). Siguientes M líneas contienen una descripción de caminos especiales, cada uno de los cuales consta de tres números enteros: u, v : un par de ciudades diferentes entre las que pasa el camino especial, y w : el costo de construir el camino correspondiente (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). La última línea contiene los números de las ciudades A y B (del 1 al N).< br />
Impresión
Imprimir un número – longitud mínima deseada. Su respuesta debe diferir de la correcta en no más de 10
−5.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |