Правительство некоторой всем известной страны решило глобально перестроить дорожную систему – оно уже успело разрушить все дороги, и теперь нужно выстроить дорожную сеть заново. Новые двусторонние дороги можно строить между любыми двумя городами, и стоимость постройки дороги равна расстоянию между соответствующими городами. Однако в некоторых случаях ландшафт позволяет построить дорогу за другую цену, такие пары городов называются особыми. Правительство решило первым делом соединить два главных города данной страны – А и Б. Вам поручили разработать план постройки дорог, при котором суммарная стоимость всех построенных дорог будет минимально возможной, и при этом по построенным дорогам можно будет добраться из города А в город Б.
Входные данные
Первая строка содержит число N – количество городов в стране (
\(1\leq N\leq10^4\)). Каждая из последующих N строк содержит по два целых числа, xi и yi – координаты соответствующего города (
\(|x|, |y| \leq 10^6\) ). Далее содержится число M – количество особых пар городов (
\(0\leq M \leq min(10^4, N(N-1)/2)\). Далее в M строках содержится описание особых дорог, каждое состоит из трех целых чисел: u, v – пара различных городов, между которыми проходит особая дорога, и w – стоимости постройки соответствующей дороги (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). В последней строке содержатся номера городов А и Б (от 1 до N).
Выходные данные
Выведите одно число – искомую минимальную длину. Ваш ответ должен отличаться от правильного не более чем на 10
−5.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 1
0 0
1 0
0 1
1
1 2 100
2 1 |
2.0000000000 |