Problem H
Treasure Diving

Legends often tell of great treasures. But you rarely get the chance to actually stumble upon those treasures. Most of them are lost in the sea, or hidden below mountains. But as you learned from one of your biggest idols, treasures do belong into a museum. And now you have the chance to make that happen.

On an expedition you found a large cave network. A native shaman has spoken about incredible values his ancestors have hidden in the caves. He even gave you an ancient map, depicting the cave network and the location of the treasures within. Sadly, the cave network is completely flooded. Since the trip out here takes forever, you decided to do a short dive and scout out the cave network. But on your arrival back at the entrance to the cave network you get the news$\ldots $ a volcano just erupted nearby. It is next to guaranteed that the lava will cover the entries to the cave network and the treasures will be lost forever.

That puts you on the spot. You only have a short time left, and only one lousy tank of air. So it is all on you. You only have time for a single dive. But how could you possible decide which route to take? The cave network is huge, and you should definitely try and rescue as much of the treasures as possible. You think back to your times as a computer scientist at the university$\ldots $ And then it hits you. You still have your laptop with you. You could write a program to help you figure out the best you can do in rescuing the treasures.

You may assume that neither locating or picking up a treasure within a cave nor the traversal of a cave consumes any air.

Input

Each test set consists of multiple test cases. The file starts with a single number $t$ ($0 < t \le 2000$) on a single line, denoting the number of testcases in the file. Each test case starts with two integers $n$ and $m$ on a single line, where $n$ the number of caves and $m$ the number of the connecting tunnels in the network ($1 \leq n \leq 10\, 000$; $0 \leq m \leq 50\, 000$). This line is followed by $m$ lines, giving a description of the tunnels of the cave as three integers $a$ $b$ and $l$ with $a$, $b$ denoting caves and $l$ giving the amount of air necessary for diving through the tunnel ($0 \le a, b < n; 0 \le l \le 500$). After the tunnels follows an integer $i$ on a single line, giving the number of idols in the cave system ($0 \leq i \leq 8$). This line is followed by a single line containing $i$ integers $p_1, \ldots , p_ i$ giving the caves withing the network conaining an idol ($0 \le p_1,\ldots ,p_ i < n$). The input is concluded by a single number, giving the liters of air $a$ you have available ($0 \le a \le 1\, 000\, 000$). You will always start (and end) at the node with the label $0$.

Output

For each test case print a number $X$ on a single line, where X is replaced by the maximal number of idols the diver can recover.

3
5 3
0 1 10
0 2 20
0 3 30
4
1 2 3 4
30
5 3
0 1 10
0 2 20
0 3 30
4
1 2 3 4
60
5 3
0 1 10
0 2 20
0 3 30
4
1 2 3 4
10000

1
2
3