Problem
Il governo di un noto paese ha deciso di ricostruire globalmente il sistema stradale – è già riuscito a distruggere tutte le strade, e ora è necessario ricostruire la rete stradale. Nuove strade a doppio senso possono essere costruite tra due città qualsiasi e il costo per costruire la strada è pari alla distanza tra le rispettive città. Tuttavia, in alcuni casi, il terreno consente di costruire una strada a un prezzo diverso, tali coppie di città sono chiamate speciali. Il governo ha deciso prima di tutto di collegare le due principali città A e B. Siete stati incaricati di sviluppare un piano per la costruzione di strade, in cui il costo totale di tutte le strade costruite sarà il più basso possibile, e allo stesso tempo, lungo le strade costruite, sarà possibile ottenere dalla città A alla città B.
Inserimento
La prima riga contiene il numero N – numero di città nel paese (
\(1\leq N\leq10^4\)). Ognuna delle seguenti N righe contiene due numeri interi, xi e yi – coordinate della città corrispondente (
\(|x|, |y| \leq 10^6\) ). Quanto segue contiene il numero M – numero di coppie speciali di città (
\(0\leq M \leq min(10^4, N(N-1)/2)\). M righe successive contengono una descrizione di strade speciali, ciascuna composta da tre numeri interi: u, v – una coppia di diverse città tra le quali passa la strada speciale, e w – il costo di costruzione della strada corrispondente (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). L'ultima riga contiene i numeri delle città A e B (da 1 a N).< br />
Impressum
Stampa un numero – lunghezza minima desiderata. La tua risposta non dovrebbe differire da quella corretta di non più di 10
−5.
Esempi
| # |
Input |
Uscita |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |