printРабочее место участника

printЗадачи

703. Заячья избушка-2

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Заяц решил построить себе новую избушку на одной из полян в лесу. Всего в лесу `N` полян, связанных между собой `K` тропинками разной длины. Между двумя полянами проложено не более одной тропинки. Тропинки не пересекаются между собой, так как прокладывались с использованием переходных мостов и подземных переходов. На полянах `A` и `B` уже построили себе домики Волк и Лиса, а Зайцу, естественно, хочется жить как можно дальше от них. Требуется выбрать полянку для строительства избушки, чтобы величина `1/a+1/b` была минимальной, где `a` – наименьшее расстояние по тропинкам от домика Зайца до домика Волка, а `b` – наименьшее расстояние от домика Зайца до домика Лисы. Если нет пути между полянами, то соответствующее слагаемое принимаем равным 0.
Во входном файле в первой строке четыре целых числа через один пробел: `N`, `K`, `A` и `B`  – количество полян и тропинок, номера полян с домиками Волка и Лисы (`3\ ≤\ N\ ≤\ 1000`, `1\ ≤\ K\ ≤\ 10000`, `1\ ≤\ A\ ≤\ N`, `1\ ≤\ B\ ≤\ N`). Далее следует `K` строк с информацией о тропинках. В каждой строке содержится три целых числа через пробел: номера двух полянок, связанных тропинкой, и длина тропинки (от 1 до 1000).
В выходной файл вывести все полянки с минимальным значением указанного выражения в порядке возрастания номеров. Каждый номер поляны выводить на отдельной строке.

Пример ввода

5 4 2 3
2 4 7
4 5 1
1 5 4
1 3 8

Вывод для примера

1
5
loading