Description

DGL's city has a total of m subway lines, numbered as Line 1, Line 2, ..., Line m. The entire city has n stations, numbered from 1 to n. The cost of taking Line i is a_i, and the cost increases by b_i for each additional station. Line i has c_i stations, and these c_i stations are known. If multiple subway lines pass through the same station, you can transfer to another line at that station, and you can transfer multiple times. Now, DGL wants to take the subway from station s to station t. The waiting time for the subway is negligible. Find the minimum cost, or output -1 if it's not possible to reach the destination.

Note that the subway is bidirectional, so you can travel in either direction along the line. 

Input

The first line contains a number T (1 ≤ T ≤ 5), indicating the number of testcases.

For each test case:

• The first line contains four positive integers n, m, s, t, representing the number of stations, the number of subway lines, the starting station, and the destination station.
• From the second line to the m+1-th line, each line contains three numbers a_i, b_i, c_i, representing the cost of taking Line i, the additional cost per station for Line i, and the number of stations on Line i. The next c_i numbers represent the station numbers on Line i.

Output

Output a single number representing the minimum cost. If it's not possible to reach the destination, output -1.

Remarks

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ 500
• 1 ≤ s, t ≤ n
• 1 ≤ a_i, b_i ≤ 100
• 1 ≤ c_i ≤ n
• ∑ c_i ≤ 10⁵

Sample Explanation

For the first testcase, Taking Line 1 costs 2 units. Moving from Station 1 to Station 3 costs 2 units. Transferring to Line 2 costs 2 units. Moving from Station 3 to Station 4 costs 1 unit. Therefore, the minimum total cost is 7 units.

For the second testcase, there is no line can go to Station 3.

Subtasks

• For testcases 1 ~ 2: m = 1
• For testcases 3 ~ 4: n, m ≤ 100
• For testcases 5~10: no other restriction.

Sample Input  Download

Sample Output  Download

Tags

Discuss