Traffic in Chefland

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
There are N cities in Chefland. Chef owns the biggest traffic company in Chefland, and Chef has built N1 bidirectional roads between these cities. The ith road connects city a_{i} and city b_{i}, and is c_{i} kms long. It's possible to travel between any two cities by going through these roads. However, only those people who have Chef's VIP card can use these roads. It costs 1 Chefcoin/km to travel on one of Chef’s roads.
A businessman named Fehc came to Chefland to compete with Chef's company and created his own traffic network. It also contains N1 roads. The ith of these roads connects city p_{i} and city q_{i}, and has length r_{i} kms. Again, it is possible to travel between any two cities by going through Fehc's roads (and ignoring Chef's). Similar to Chef, only those people who have Fehc's VIP card can travel on these roads and it costs 1 Chefcoin/km to travel on one of Fehc's roads.
On New Year's Day in Chefland, there is expected to be a huge traffic flow because of people travelling to celebrate with family and friends. For any 1 ≤ i < j ≤ N, there will be exactly one person who wants to go from city i to city j. To achieve this, he should ask Chef or Fehc for VIP cards and travel along the roads permitted by the cards. However, Chef and Fehc are in a competing relationship, and hence any one person can only get one VIP card. A person will choose that company that has a shorter(cheaper) route from city i to city j, buy that company's VIP card, and travel along that company's roads. If there is a tie, he chooses an arbitrary company(this doesn't affect the answer of the problem).
There are M=N*(N1)/2 people who will travel on New Year's Day. Your task is to compute the total amount of Chefcoins spent by them.
Input
 The first line of input contains a single integer T denoting the number of test cases.
 For each test case, the first line contains a single integer N denoting the number of cities in Chefland.
 The next N1 lines each contain three spaceseparated integers a_{i}, b_{i} and c_{i}, denoting a road by Chef's company.
 The next N1 lines each contain three spaceseparated integers p_{i}, q_{i} and r_{i}, denoting a road by Fehc's company.
Output
For each test case, output one number denoting the total amount of Chefcoins that will be spent by the M travellers.
Constraints
 1 ≤ T ≤ 1000
 2 ≤ N ≤ 50000
 the sum of N over all test cases ≤ 200000
 1 ≤ a_{i}, b_{i}, p_{i}, q_{i} ≤ N
 1 ≤ c_{i}, r_{i} ≤ 4096
Subtask #1 (8 points):
 N ≤ 1000
 the sum of N over all test cases ≤ 5000
Subtask #2 (10 points):
 For any 1 ≤ i < N, a_{i} = p_{i}, b_{i} = q_{i}, c_{i} = r_{i}. In other words, Chef's and Fehc's traffic networks are exactly the same.
Subtask #3 (23 points):
 Fehc's traffic network is a chain 123...N
Subtask #4 (59 points):
 original constraints
Example
Input: 2 3 1 2 3 2 3 2 1 3 2 2 3 3 6 4 3 2 4 5 2 2 4 2 4 6 2 1 5 1 6 3 2 1 5 1 2 4 1 6 5 1 4 6 2 Output: 7 39
Explanation
Example case 1: There are 3 people:
 The first person goes from city 1 to city 2. He chooses Chef's roads and pays 3 chefcoin.
 The second person goes from city 1 to city 3. He chooses Fehc's roads and pays 2 chefcoin.
 The third person goes from city 2 to city 3. He chooses Chef's roads and pays 2 chefcoin.
Author:  r_64 
Editorial  https://discuss.codechef.com/problems/CHEFTRAF 
Tags  centroiddecomp, dfsorder, fenwicktree, hard, lca, ltime52, r_64 
Date Added:  22092017 
Time Limit:  9 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 