5362: Destinations
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
There are n towns in Byteland, labeled by 1,2,…,n, connected by n−1 bidirectional roads like a tree. m tourists are going to visit Byteland, the i-th of which will start his journey at the si-th town. However, none of them has decided where to end his journey. Formally, for the i-th tourist, he has made 3 plans, the j-th of which will end at the ei,j-th town, and will cost him ci,j dollars. When a tourist makes his decision, he will walk along the shortest path to visit all the towns from si to his destination. Note that ei,j can coincide with si, the si-th town and the destination town will also be visited by the i-th
tourist. Two plans may share the same destination but may differ in
cost because the tourist may do extremely different things in the same
town.
They will share photos of their journeys in Byteland. Nobody is willing to visit the same place with others. Your task is to help each tourist choose his destination from his plans such that each town will be visited by at most one tourist, and the total cost for all the tourists is minimized, or determine it is impossible.
They will share photos of their journeys in Byteland. Nobody is willing to visit the same place with others. Your task is to help each tourist choose his destination from his plans such that each town will be visited by at most one tourist, and the total cost for all the tourists is minimized, or determine it is impossible.
输入
The first line contains a single integer T (1≤T≤500), the number of test cases. For each test case:
The first line of the input contains two integers n and m (1≤n≤200000, 1≤m≤100000), denoting the number of towns and the number of tourists.
Each of the next n−1 lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), denoting a bidirectional road between ui and vi. It is guaranteed that the roads form a tree.
In the next m lines, the i-th line contains seven integers si, ei,1, ci,1, ei,2, ci,2, ei,3 and ci,3 (1≤si,ei,j≤n, 1≤ci,j≤106), describing the i-th tourist.
It is guaranteed that the sum of all n is at most 1000000, and the sum of all m is at most 300000.
The first line of the input contains two integers n and m (1≤n≤200000, 1≤m≤100000), denoting the number of towns and the number of tourists.
Each of the next n−1 lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), denoting a bidirectional road between ui and vi. It is guaranteed that the roads form a tree.
In the next m lines, the i-th line contains seven integers si, ei,1, ci,1, ei,2, ci,2, ei,3 and ci,3 (1≤si,ei,j≤n, 1≤ci,j≤106), describing the i-th tourist.
It is guaranteed that the sum of all n is at most 1000000, and the sum of all m is at most 300000.
输出
For each test case, print a single line containing an integer denoting the minimum total cost. If there is no solution, print ''-1'' instead.
样例输入 复制
2
7 2
1 2
1 3
2 4
2 5
3 6
3 7
2 1 1 3 100 4 200
3 2 1 4 2 7 50
4 2
1 2
2 3
3 4
1 2 1 3 1 4 1
2 1 1 3 1 4 1样例输出 复制
51
-1