printЗанятие 12

printD. Заячья избушка

Ограничения: время – 500ms/1000ms, память – 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≤20,\ 1≤K≤100,\ 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