Outpost Navigation

Zombies have taken over the city and your team is running low on supplies. After careful scouting you have a map that lists the safe outposts along with a report of how many zombies were spotted on each road. Every outpost belongs to the same radio network and goes by its radio call sign.

Your team carries a limited amount of ammunition, so it can only hold off a zombie group up to a certain size. One unit of ammunition holds off one zombie for one trip. To travel a road safely you must spend as much ammunition as the number of zombies you encounter on that road. Using the reconnaissance data, find the path to an outpost with the supplies you need that is safe and has the fewest zombie encounters.

You begin at the first outpost in the list and set out with all of the ammunition stored there. Apart from the starting outpost, at most one other outpost has ammunition without having the supplies you need. If you travel to that outpost, you may collect all of its ammunition. Any number of outposts may hold the supplies you need, and you only have to reach one of them.

If you have to travel a road more than once, every later trip meets the same number of zombies as the first one, and those zombies count as extra encounters. Zombies are not easily killed with bullets.

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

The first line of each test case contains the number of outposts $N$ ($1 \le N \le 100$) and the number of roads $R$ ($0 \le R \le 200$), separated by a space.

Each of the next $N$ lines describes one outpost and contains, in order, its call sign, the amount of ammunition $A$ ($0 \le A \le 100$) stored there, and a string telling whether the outpost has the supplies you need. A call sign is 6 characters long and uses the uppercase letters A to Z and the digits 0 to 9, and the last string is either yes or no. The first outpost in the list is where you start.

Each of the next $R$ lines describes one road and contains, in order, the call signs of the two outposts it connects and the number of zombies $Z$ ($0 \le Z \le 100$) you encounter on it. A road can be traveled in both directions.

For each test case, print on a single line the smallest number of zombie encounters on a safe path to an outpost with the supplies you need. If no safe path exists, print No safe path instead.