Hide

Problem K
Destination Unknown

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?

\includegraphics{sample2.png}
Figure 1: 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.

Input

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$ ($2 \le n \le 2\, 000$, $1 \le m \le 50\, 000$ and $1 \le t \le 100$): 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$ ($1 \le s, g, h \le n$): the intersection the duo started from and the two intersections between which the duo has traveled, with $g \neq h$.

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

  • $t$ lines with one integer $x$ ($1 \le x \le n$): 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.

Output

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.

Sample Input 1 Sample Output 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
4 5
6

Please log in to submit a solution to this problem

Log in