H. Shelter in the Rain
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a weighted undirected graph with $$$n$$$ nodes and $$$m$$$ edges. Each edge has a weight $$$w$$$, representing the time required to travel through that edge.

You start at node $$$a$$$ and want to reach node $$$b$$$.

Some nodes contain shelters. If you arrive at a shelter, you may stop and rest there. Resting resets your continuous travel time counter to zero, and resting does not add to the travel time.

It is raining, and you cannot travel continuously under the rain for more than $$$k$$$ units of time.

Formally, along any path from $$$a$$$ to $$$b$$$, the sum of edge weights between two consecutive shelter nodes must not exceed $$$k$$$. The same restriction also applies between the start node $$$a$$$ and the first shelter visited, and between the last shelter visited and the destination node $$$b$$$.

Determine whether it is possible to reach node $$$b$$$ from node $$$a$$$ while respecting this constraint.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

For each test case:

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$0 \le m \le 2\cdot10^5$$$, $$$0 \le k \le 10^9$$$) — the number of nodes, the number of edges, and the maximum allowed continuous travel time under the rain.

The second line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a,b \le n$$$) — the starting node and the destination node.

The third line contains an integer $$$s$$$ ($$$0 \le s \le n$$$) — the number of nodes that contain shelters.

The fourth line contains $$$s$$$ integers $$$s_1, s_2, \ldots, s_s$$$ ($$$1 \le s_i \le n$$$) — the nodes that contain shelters.

Each of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$1 \le w_i \le 10^9$$$) describing an undirected edge between nodes $$$u_i$$$ and $$$v_i$$$ with travel time $$$w_i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case, print YES if it is possible to reach node $$$b$$$ from node $$$a$$$ while respecting the rain constraint. Otherwise, print NO.

Example
Input
5
3 2 6
1 3
1
2
1 2 3
2 3 3
3 2 4
1 3
1
2
1 2 3
2 3 3
2 1 10
1 2
0
1 2 7
4 3 4
1 4
1
3
1 2 3
2 3 3
3 4 3
6 5 6
1 6
2
3 5
1 2 3
2 3 3
3 4 3
4 5 3
5 6 3
Output
YES
YES
YES
NO
YES
Note

In the second test case, the path $$$1 \to 2 \to 3$$$ is valid. Although the total length of the path is $$$6$$$, the traveler stops at node $$$2$$$, which is a shelter. This resets the rain timer before continuing the journey.

In the fourth test case, although node $$$3$$$ contains a shelter, it cannot be reached from node $$$1$$$ without exceeding the limit $$$k$$$. Therefore, it is impossible to reach the destination.

In the fifth test case, the traveler first goes $$$1 \to 2 \to 3$$$ (total time $$$6$$$) and rests at shelter $$$3$$$. Then they continue $$$3 \to 4 \to 5$$$ (total time $$$6$$$) and rest again at shelter $$$5$$$. Finally, they travel $$$5 \to 6$$$ (time $$$3$$$), successfully reaching the destination.