Train Trip
Leha and his two friends have formed a programming team and are going to this year's ACM ICPC which takes place in their home country. They decided to travel by train to the city where the contest takes place. And, they want to minimize the train trip expenses.
The railway system of the country is represented as an undirected connected graph of vertices numbered from to with edges between them (vertices represent stations). Initially, Leha is in the vertex . The two other members of his team are in and respectively (note that are not necessarily distinct). A person can move from their current vertex, say , to vertex if there is an edge between and in the graph. The cost of travel is different depending on the number of people crossing the edge at the same time. If one person is crossing the edge, the cost is equal to . If two people are crossing the same edge together, the cost is . And if all three are crossing the same edge together, they have to pay .
The contest takes place in vertex . You have to help Leha's team find the minimal total cost that they have to pay for the tickets if Leha and his team move optimally.
Input Format
The first line contains a single integer denoting the number of test cases.
The first line of each test case contains a single integer denoting the number of vertices in the graph.
The second line of each case contains three space-separated integers denoting the respective values of , , .
The third line contains three space-separated integers denoting the respective values of , , .
The th of the subsequent lines contain two space-separated integers denoting the values of , the description of the th edge.
Constraints
- All edges connect different vertices.
- The sum of in a file is .
Subtasks
- For one third of the total score, the sum of in a file is .
Output Format
For each test case, print a single integer denoting the team's minimal total cost of the trip.
Sample Input 0
2
5
2 1 1
4 5 3
1 2
1 3
2 4
2 5
5
2 2 2
4 5 3
1 2
1 3
2 4
2 5
Sample Output 0
7
8
Explanation 0
The following image illustrates the first sample case:
The optimal strategy is for the team member at vertex to go directly to vertex and the other two team members at vertices and to meet at vertex and then go together towards vertex . The total cost is which is the smallest possible cost for everyone to reach vertex .
The second sample case represents the same setup with the costs changed. In this case, it turns out that the optimal strategy is still the same, but the cost is now .
xxxxxxxxxxwith Ada.Text_IO, Ada.Integer_Text_IO;use Ada;procedure Solution is-- Enter your code here. Read input from STDIN. Print output to STDOUTend Solution