Назначение неизвестно
Вы агент B100. Пара ярко одетых цирковых артистов путешествует по дорогам города, и ваша задача — выяснить, куда они направляются. Известно, что они начали свой путь в точке s и движутся к одному из нескольких возможных пунктов назначения. Они очень спешат, поэтому мы уверены, что они не будут делать крюк по пути к своей цели.
К сожалению, несмотря на их яркие наряды, дуэт нигде не видно. К счастью, у вас есть исключительное обоняние. Вы можете почувствовать, что они прошли по дороге между перекрестками g и h.
Куда направляется этот неуловимый дуэт? Или мы все еще не уверены?
Визуальное представление второго примера. Дуэт путешествует от серого круга к одному из двух черных кругов, и вы почувствовали их на пунктирной линии, так что они могут направляться к 6.
Входные данные
На первой строке указано одно положительное число: количество тестов, не более 100. Далее для каждого теста:
Одна строка с тремя целыми числами, разделенными пробелами: n, m и t (2 ≤ n ≤ 2000, 1 ≤ m ≤ 50000 и 1 ≤ t ≤ 100): количество перекрестков в городе, количество дорог между ними и количество возможных пунктов назначения соответственно.
Одна строка с тремя целыми числами, разделенными пробелами: s, g и h (1 ≤ s, g, h ≤ n): перекресток, с которого дуэт начал, и два перекрестка, между которыми дуэт прошел, при этом g ≠ h.
m строк с тремя целыми числами, разделенными пробелами: a, b и d (1 ≤ a < b ≤ n и 1 ≤ d ≤ 1000), указывающими, что между перекрестками a и b есть двусторонняя дорога длиной d.
t строк с одним целым числом x (1 ≤ x ≤ n): возможные пункты назначения. Все возможные пункты назначения различны и все они отличаются от s.
Между парой перекрестков может быть не более одной дороги. Одна из m строк описывает дорогу между g и h. Эта дорога гарантированно находится на кратчайшем пути к как минимум одному из возможных пунктов назначения.
Выходные данные
Для каждого теста:
Одна строка с одним или несколькими целыми числами, разделенными пробелами, указывающими на пункты назначения, к которым дуэт все еще может направляться, в порядке возрастания.