Treasure Diving

Legends often tell of great treasures, but you rarely get the chance to actually stumble upon them. Most are lost at sea or hidden below mountains. Yet, as one of your idols taught you, treasures belong in a museum — and now you have the chance to make that happen.

On an expedition you found a large cave network. A local shaman told you of the incredible riches his ancestors hid in the caves, and even gave you an ancient map showing the network and where the treasures lie. Sadly, the cave network is completely flooded. Since the trip out here takes forever, you decide on a short dive to scout the caves. But when you resurface at the entrance you hear the news: a nearby volcano has just erupted. The lava is all but certain to seal the entrances, and the treasures will be lost forever.

That puts you on the spot. You have very little time and only a single tank of air, so it is all on you — you have time for just one dive. How can you decide which route to take? The network is huge and you should rescue as many treasures as possible. You think back to your days as a computer scientist... and it hits you: you still have your laptop. You can write a program to work out the best you can do.

You may assume that neither locating nor picking up a treasure inside a cave, nor passing through a cave, consumes any air; only diving through a tunnel does.

Each test set consists of multiple test cases. The input begins with a single number t (0 < t ≤ 2000) on its own line, the number of test cases.

Each test case starts with two integers n and m on one line, where n is the number of caves and m is the number of connecting tunnels (1 ≤ n ≤ 10 000; 0 ≤ m ≤ 50 000). The next m lines each describe a tunnel with three integers a, b and l, where a and b are caves and l is the air needed to dive through that tunnel (0 ≤ a, b < n; 0 ≤ l ≤ 500). After the tunnels comes an integer i on its own line, the number of idols in the cave system (0 ≤ i ≤ 8), followed by a line with i integers p1, ..., pi giving the caves that contain an idol (0 ≤ p1, ..., pi < n). The test case ends with a single number a, the liters of air you have available (0 ≤ a ≤ 1 000 000). You always start and end at the cave labelled 0.

For each test case, print a single line with one number: the maximum number of idols the diver can recover.