Problem
O governo de algum país conhecido decidiu reconstruir globalmente o sistema rodoviário – já conseguiu destruir todas as estradas, e agora é preciso reconstruir a rede viária. Novas estradas de mão dupla podem ser construídas entre quaisquer duas cidades, e o custo para construir a estrada é igual à distância entre as respectivas cidades. Porém, em alguns casos, o terreno permite construir uma estrada por um preço diferente, esses pares de cidades são chamados de especiais. O governo decidiu antes de tudo conectar as duas principais cidades deste país – A e B. Você foi instruído a desenvolver um plano para a construção de estradas, no qual o custo total de todas as estradas construídas seja o mais baixo possível e, ao mesmo tempo, ao longo das estradas construídas, será possível obter da cidade A para a cidade B.
Entrada
A primeira linha contém o número N – número de cidades no país (
\(1\leq N\leq10^4\)). Cada uma das seguintes N linhas contém dois números inteiros, xi e yi – coordenadas da cidade correspondente (
\(|x|, |y| \leq 10^6\) ). O seguinte contém o número M – número de pares especiais de cidades (
\(0\leq M \leq min(10^4, N(N-1)/2)\). Próximas M linhas contêm uma descrição de estradas especiais, cada uma composta por três números inteiros: u, v – um par de cidades diferentes entre as quais a estrada especial passa e w – o custo de construção da estrada correspondente (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)).A última linha contém os números das cidades A e B (de 1 a N).< br />
Impressão
Imprima um número – comprimento mínimo desejado. Sua resposta deve diferir da correta em no máximo 10
&menos;5.
Exemplos
| # |
Entrada |
Saída |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |