eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Destination Unknown

Destination Unknown

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

You are agent B100. A pair of prominently dressed circus artists is traveling over the roads of the city and your mission is to find out where they are headed. All we know is that they started at point s and that they are heading for one of several possible destinations. They are in quite a hurry, though, so we are sure they will not take a detour to their destination.

Alas, prominently dressed as they may be, the duo is nowhere to be seen. Fortunately, you have an exceptional sense of smell. More specifically: your nose will never let you down. You can actually smell they have traveled along the road between intersections g and h.

Where is the elusive duo headed? Or are we still not sure?

A visual representation of the second sample. The duo is travelling from the gray circle to one of the two black circles, and you smelled them on the dashed line, so they could be heading to 6.

Входные данные

On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • One line with three space-seperated integers n, m and t (2n2000, 1m50000 and 1t100): the number of intersections in the city, the number of individual roads between those intersections, and the number of possible destinations respectively.

  • One line with three space-seperated integers s, g and h (1s, g, hn): the intersection the duo started from and the two intersections between which the duo has traveled, with gh.

  • m lines with three space-separated integers a, b and d (1a < bn and 1d1000), indicating that there is a bidirectional road between intersections a and b of length d.

  • t lines with one integer x (1xn): the possible destinations. All possible destinations are distinct and they are all different from s.

There is at most one road between a pair of intersections. One of the m lines describes the road between g and h. This road is guaranteed to be on a shortest path to at least one of the possible destinations.

Выходные данные

Per test case:

  • One line with one or more space-separated integers, indicating the destinations that the duo can still be headed for, in increasing order.

Пример

Входные данные #1
2
5 4 2
1 2 3
1 2 6
2 3 2
3 4 4
3 5 3
5
4
6 9 2
2 3 1
1 2 1
1 3 3
2 4 4
2 5 5
3 4 3
3 6 2
4 5 4
4 6 3
5 6 7
5
6
Выходные данные #1
4 5
6
Источник The 2013 Benelux Algorithm Programming Contest, BAPC 2013