Problem
Le gouvernement d'un pays bien connu a décidé de reconstruire globalement le réseau routier – il a déjà réussi à détruire toutes les routes, et maintenant il faut reconstruire le réseau routier. De nouvelles routes à double sens peuvent être construites entre deux villes, et le coût de construction de la route est égal à la distance entre les villes respectives. Cependant, dans certains cas, le terrain vous permet de construire une route pour un prix différent, de telles paires de villes sont dites spéciales. Le gouvernement a décidé tout d'abord de relier les deux principales villes de ce pays – A et B. Vous avez été chargé d'élaborer un plan de construction de routes, dans lequel le coût total de toutes les routes construites sera aussi bas que possible, et en même temps, le long des routes construites, il sera possible d'obtenir de la ville A à la ville B.
Entrée
La première ligne contient le nombre N – nombre de villes du pays (
\(1\leq N\leq10^4\)). Chacune des N lignes suivantes contient deux entiers, xi et yi – coordonnées de la ville correspondante (
\(|x|, |y| \leq 10^6\) ). Ce qui suit contient le numéro M – nombre de paires spéciales de villes (
\(0\leq M \leq min(10^4, N(N-1)/2)\). M lignes suivantes contiennent une description des routes spéciales, chacune composée de trois nombres entiers : u, v - une paire de villes différentes entre lesquelles passe la route spéciale, et w - le coût de construction de la route correspondante (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). La dernière ligne contient les numéros des villes A et B (de 1 à N).< br />
Mentions légales
Imprimez un numéro – longueur minimale souhaitée. Votre réponse ne doit pas différer de la bonne réponse de plus de 10
−5.
Exemples
| # |
Entrée |
Sortie |
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |