Q13: Node weighted Shortest Paths

Consider an directed graph in which the nodes are weighted, while the edges aren't. The weight of a path is now defined as the sum of the weights of the nodes that it uses. Given two nodes, design algorithm that will determine the shortest path between them. If there are negative cycles, the algorithm should detect it.

Submit this problem as "Q13" in the judge.

INPUT

There will be multiple test cases. The first line will contain an integer numCase equal to the number of test cases.
For each test case, the first line will contain an integer n representing the number of nodes (2 <= n <= 400). The next line contains two integers a, b representing the start and end node. Nodes are numbered from 0 to n-1. The next n lines will contain descriptions of the graph nodes (from 0 to n-1) in the following format:

u w a1 a2 .. ak

which means the there node u has weight w, and there is an edge from u to node a1 a2 ... ak. Weights will be between -1000 to 1000. u will start at 0 and end at n-1. The graph will be connected: there is a path from everynode to every other node.

OUTPUT

For each test case, output the weighted length of the shortest path between a and b. If there is a negative cycle, output "Negative Infinity".

Sample Input

2
4
0 3
0 5 1 2
1 -2 0 3
2 4 3
3 5
4
0 3
0 5 1 2
1 -2 0 3
2 4 3
3 -10 0

Sample Output

8
Negative Infinity