Imagine a planet with two beautiful islands. Each island is decorated with several cities, and they are connected by a network of bidirectional roads. The cost of traveling through each road is provided. Both the islands have equal number of cities and roads.
You are given two arrays, A and B, where A represents the beauty index associated with the cities on Island 1, and B represents the beauty index associated with the cities on Island 2.
To journey from a city i on Island 1 to a city j on Island 2, there exists special unidirectional flights. However, specific conditions must be met:
- j must be a multiple of i, indicating a compatible connection between the cities. (i.e. a unidirectional flight exists between city i to city j if and only if j is a multiple of i)
- The cost of the flight is determined by multiplying the beauty indexes of ith city and jth city (i.e. A[i]∗b[j]), ensuring a harmonious transition between the islands.
Your task is to calculate the minimum cost required to travel from city x on Island 1 to city y on Island 2. If it is not possible to travel from city x to city y based on the given conditions, you should output −1, indicating an incompatible connection.
Input format
- First line contains an integer T, the number of test cases.
- The first line of each test case contains 2 integers N, M seperated by a space representing the number of cities and roads respectively.
- The next line contains N integers space-seperated by a space representing the array A
- The next line contains N integers space-seperated by a space representing the array B
- The next M lines of each test case contains 3 space-seperated integers X, Y, Z representing a bidirectional road from city X of 1st island to city Y of 1st island and it requires a cost Z to travel through that road.
- The next M lines of each test case contains 3 space-seperated integers X, Y, Z representing a bidirectional road from city X of 2nd island to city Y of 2nd island and it requires a cost Z to travel through that road.
- The next line of each test case contains 2 space-seperated integers x, y which are described in the problem statement.
- It is guaranteed that there are no self loops or multiple edges in the graphs.
Output format
For each testcase, output an integer, the minimum cost required to travel from city x in 1st island to city y in 2nd island. Or print −1 if it's an incompatible connection in a new line.
Constraints
- 1≤T≤2∗105
- 3≤N≤4∗105
- 1≤M≤4∗105
- 1≤A[i]≤109
- 1≤B[i]≤109
- 1≤X,Y≤N,1≤Z≤109
- 1≤x,y≤N
- Also it's guaranteed that the sum of N, M over all test cases doesn't exceed 4∗105
3 5 7 1 2 3 4 5 10 9 8 7 6 1 2 1 1 3 3 1 4 10 1 5 5 2 5 4 2 4 2 3 4 3 1 5 1 2 4 2 2 5 1 3 1 3 3 2 4 3 4 5 3 5 1 4 5 3 2 1 1 1 1 1 1 1 2 1 2 3 1 1 3 1 2 1 1 2 3 4 2 1 1 1 1 1 1 1 1 1 2 1 1 4 1 1 2 1 1 4 1 3 4
- For test case 1: one possible path to go from city 4 of island 1 to city 5 of island 2 is as follows -:
- Go from city 4 of island 1 to city 2 of island 1 by incurring a cost of 2
- Then go from city 2 of island 1 to city 1 of island 1 by incurring a cost of 1
- Then take a flight and go from city 1 of 1st island to city 5 of 2nd island incurring a cost of A[1]∗B[5]= 1∗6 = 6 (here 5 is a multiple of 1, so the flight exists)
- Total cost is 2+1+6 = 9, and it can be proved that this is the minimum cost required to go from city 4 of island 1 to city 5 of island 2
- For test case 2: one possible path to go from city 2 of island 1 to city 3 of island 2 is as follows -:
- Go from city 2 of island 1 to city 3 of island 1 by incurring a cost of 1
- Then take a flight from city 3 of 1st island to city 3 of 2nd island incurring a cost of A[3]∗B[3] = 1∗1 = 1 (here 3 is a multiple of 3, so the flight exists)
- Total cost is 1 + 1 = 2, and it can be proved that this is the minimum cost required to go from city 2 of island 1 to city 3 of island 2
- For test case 3: it can be proved that no path exists from city 3 in island 1 to city 4 in island 2
