Matrix

After years of searching, Morpheus found The One: a computer programmer named Thomas A. Anderson, known to his friends as Neo. On the way back from the Oracle, Morpheus reached the real world first, and an agent destroyed the telephone before Neo could pick it up. Neo has not reached his full potential yet, so he has to run to another telephone without fighting an agent.

The Matrix world has $N$ locations, and Neo stands at location $0$. There are $M$ paths connecting locations. Every path is bidirectional and takes a fixed amount of time to walk. You know where the agents are and where the telephones are.

You do not know how the agents move, so assume the worst case. If some agent can reach location $v$ in $D_v$ minutes at the earliest, then from time $D_v$ on there may be an agent standing at $v$. Neo may therefore pass only through locations he reaches strictly before $D_v$. Arriving exactly at time $D_v$ counts as meeting an agent. The same rule applies to a location that holds a telephone: if Neo and an agent reach the telephone at the same time, Neo has to fight the agent before picking up the phone.

Neo starts at location $0$ at time $0$ and never stops on the way. If he can reach some telephone safely, report the earliest arrival time among those telephones. If he cannot reach any telephone safely, report that instead.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

The first line of each test case contains four integers $N$, $M$, $NA$, $NT$: the number of locations, the number of paths, the number of agents, and the number of telephones. ($3 \le N \le 1000$, $1 \le M \le 100000$, $NA > 0$, $NT > 0$, $NA + NT < N - 1$)

Each of the next $M$ lines contains three integers $u$, $v$, $m$ ($0 \le u, v < N$, $1 \le m \le 30$), meaning that a path connects location $u$ and location $v$ and takes $m$ minutes to walk. Several paths may connect the same pair of locations, and $u$ may equal $v$.

The next line contains the $NA$ locations of the agents.

The last line contains the $NT$ locations of the telephones.

Location $0$ holds no agent and no telephone. No location holds both an agent and a telephone. The sum of $N$ over all test cases is at most $20000$, and the sum of $M$ is at most $200000$.

Print one line per test case. If no telephone can be reached safely, print Neo may fight an Agent. Otherwise print the minimum time in minutes needed to get out of the Matrix, as an integer.