One day in a faraway city, Ronny, a famous scientist, was stuck in traffic once again. This thing happens everyday when he tries to get back home from work. But this time it was different, Ronny was working in a project that includes these situations about traffic and stuff. So in the middle of this dense traffic, Ronny started to think about a very interesting problem that includes traffic and how the cities are connected, including their avenues and intersections. The problem goes like this: There are at most N cities, connected by at most M roads. These roads are in one direction, so if you can go from city A to city B, then you can’t go from city B to city A. Following this scheme, every road will lead always forward from Ronny’s work to Ronny’s house.

In a city i there are at most Ai avenues and at most Ii intersections, these ones are not in a singular direction. If an avenue Z let you go from the intersection X to intersection Y, then the same avenue Z will let you go from Y to X. Due the horrible traffic that hits the cities everyday and the smoke derived from it, the authorities of each one of them will close a bunch of roads, allowing only one way from intersection 1 to intersection Ii. This only way will be the way with the maximum capacity, i.e., there exist no other way with a higher capacity than this. Obviously, the capacity of this way is determined by the street with the minimum capacity.

Due to the horrible traffic that hit the cities everyday, the authorities of each city close some avenues to avoid the city to overheat with the cars’ smoke. Of course, they will keep open those avenues that leads from the beginning to the end of the city, i.e., from intersection 1 to intersection Ii. Beside that, the authorities will close exactly those avenues that are strictly not necessarily to maximize the amount of vehicles that can transit in the city at a time. Fortunately, Ronny knows every little detail about the problem, even data! But not the answers. He will give you all the data of the problem, i.e., the number of cities, how are they connected, and the structure of each city, their avenues and how they connect their intersections. You may know that every road that goes from city A to city B, connects the last intersection of city A to the first intersection of city B.

Ronny need your help to figure out what's the maximum amount of vehicles that can go from Ronny’s work to Ronny’s house at a time.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Every test case will have a line with 2 integers, N and M. Then N descriptions will follow, with a string Name (That represents the name of the city, this one will contain only lower case letters) and 2 integers Ii and Ai. Then Ai lines with 3 integers, X, Y and Cap; this mean that there is an avenue between the intersections X and Y with a capacity of Cap vehicles.

After all N descriptions, M lines will follow, with 2 strings, S and D, and one integer C. This indicates that exists a road that goes from city S to city D with capacity of C vehicles at a time. You should know that Ronny’s house and Ronny’s work are valid cities, but they’re not included on the N cities that were mentioned before. These ”special” cities are going to be called "ronnys_house" and "ronnys_work". It is sure that it will exist at least one way to get from Ronny’s work to Ronny’s house.

Output

For each input case you must print "Scenario #i: " where i is the number of the test case that you are evaluating (Starting by 1). Then you have to print a single integer that maximum amount of vehicles that can transit from Ronny’s house to Ronny’s work.

Sample

Input
2
2 4
caracas 4 4
1 2 2
1 3 2
2 3 2
2 4 1
valencia 4 5
1 2 2
1 3 3
1 4 5
2 4 1
3 4 1
ronnys_work caracas 4
ronnys_work valencia 5
caracas ronnys_house 2
valencia ronnys_house 3
4 7
caracas 4 4
1 2 2
1 3 2
2 3 2
2 4 1
valencia 4 4
1 2 2
1 3 3
1 4 5
3 4 1
maracay 3 2
1 2 2
2 3 2
maracaibo 5 6
1 3 5
1 4 2
2 3 4
2 4 4
2 5 3
4 5 4
ronnys_work caracas 4
ronnys_work maracaibo 5
ronnys_work maracay 3
caracas valencia 2
maracay valencia 3
valencia ronnys_house 4
maracaibo ronnys_house 3

Output
Scenario #1: 4
Scenario #2: 6

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100
• 1 ≤ Ii ≤ 30
• 1 ≤ |S|, |D|, |Name| ≤ 20
• 1 ≤ X, Y ≤ Ii
• 1 ≤ C, Cap ≤ 10,000