Задача №3345. Проложи дорогу (BC)
Правительство некоторой всем известной страны решило глобально перестроить дорожную систему – оно уже успело разрушить все дороги, и теперь нужно выстроить дорожную сеть заново. Новые двусторонние дороги можно строить между любыми двумя городами, и стоимость постройки дороги равна расстоянию между соответствующими городами (здесь понимается расстояние между точками на плоскости). Однако в некоторых случаях ландшафт вынуждает построить дорогу за другую цену, такие пары городов называются особыми. Правительство решило первым делом соединить два главных города данной страны – А и Б. Вам поручили разработать план постройки дорог, при котором суммарная стоимость всех построенных дорог будет минимально возможной, и при этом по построенным дорогам можно будет добраться из города А в город Б.
Первая строка содержит число \(N\) – количество городов в стране (\(1 \leq N \leq 10^4\)). Каждая из последующих \(N\) строк содержит по два целых числа, \(x_i\) и \(y_i\) – координаты соответствующего города (\(|x_i|, |y_i| \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}\).
4 1 1 0 0 1 0 0 1 1 1 2 100 2 1
2.0000000000