Задача S. Перехватчик

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Пусть имеется неориентированный граф, по ребрам которого движутся два гонщика (игрока). Каждому ребру такого графа ставится в соответствие целый положительный вес, обозначающий его длину. Полагается, что за одну единицу времени каждый гонщик проходит ровно одну единицу пути.

Известно, что первый игрок изначально выбирает оптимальный для себя маршрут. В случае, если для него существует несколько таких маршрутов, он может выбрать любой из них.

Второй игрок задумал перехватить своего соперника до того, как тот достигнет финишной вершины. С этой целью он хочет дождаться его в одной из промежуточных вершин.

Чтобы помочь 2-му игроку, необходимо определить номера тех вершин, через которые гарантированно (независимо от выбранного пути) пройдет 1-й игрок. После чего из числа таких вершин выбрать те, до которых 2-й игрок сможет добраться не позднее, чем это сделает 1-й.

Формат входного файла

В начале входного файла "input.txt" записаны два натуральных числа: n — число вершин и m — число соединяющих их ребер.

Далее следует набор из m таких ребер, каждое из которых представлено тройкой целых чисел: (ai, bi) — номера вершин, wi — вес ребра. При этом полагается, что нумерация вершин начинается с нуля.

В конце входного файла хранятся три числа f, p1 и p2, указывающие номер финишной вершины и стартовые позиции каждого из игроков.

Формат выходного файла

Выходной файл "output.txt" должен содержать список из номеров вершин, удовлетворяющих условию задачи.

В случае, если таковых нет, выходной файл следует оставить пустым.

Ограничения

Гарантируется, что исходный граф является связным.

2 ≤ n ≤ 1000, 1 ≤ m ≤ (n ⋅ (n − 1)) / 2,

0 ≤ (ai, bi) < n, 0 < wi ≤ 1000,

p1 ≠ p2

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
8 9

0 1 1
5 1 1
5 6 2
6 4 3
5 4 7
1 2 2
2 4 4
3 7 5
7 4 6

3
0
5
1
4
7
3
2
8 9

5 6 1
6 4 4
0 1 2
1 7 1
7 2 2
1 4 4
1 2 4
4 2 1
2 3 7

3
0
5
 

0.084s 0.018s 15