Chef and Chefcoin

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Everybody's heard about Chefland — the digital country where dreams come true, where nobody hears about crime and where everyone can get Accepted without submitting solutions. Of course, Chefland has the shape of a tree — there are N servers and N1 bidirectional channels connecting pairs of servers in such a way that there is exactly one path between each pair of servers.
The citizens in Chefland are living online; each citizen lives on exactly one server at any point in time. Don't be surprised, it's a futuristic scenario! Each channel connecting two servers has a value called ping. Each citizen can move to a different server through channels; moving through a channel with ping 2w takes w nanoseconds. Initially, there are c_{i} citizens living on the ith server (for each 1 ≤ i ≤ N).
Recently, Chef has created an ICO for Chefcoin — the cryptocurrency of the future in Chefland. Everyone in Chefland should receive exactly 1 Chefcoin. How to organize this process? Chefcoins can only be received on certain servers containing cryptoexchanges. Unfortunately, Chef can only create cryptoexchanges on two servers, since they consume a lot of electric power. The citizens want to receive Chefcoin as fast as possible; therefore, each citizen chooses the closest server with a cryptoexchange and moves to that server. Receiving Chefcoin at a cryptoexchange takes zero time.
Chef wants to minimize the sum of the times each citizen needs to spend moving to receive Chefcoin. The two servers containing cryptoexchanges can be chosen arbitrarily. Compute the minimum total time it takes Chefland's citizens to receive Chefcoin!
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains a single integer N.
 The second line contains N spaceseparated integers c_{1}, c_{2}, ..., c_{N}.
 N1 lines follow. Each of these lines contains three spaceseparated integers u, v and w denoting a channel with ping 2w nanoseconds connecting servers u and v.
Output
For each test case, print a single line containing one integer — the minimal sum of times it takes each citizen to receive Chefcoin if the two cryptoexchanges are placed optimally.
Constraints
 2 ≤ N ≤ 50000
 1 ≤ c_{i} ≤ 50000 for each valid i
 1 ≤ w ≤ 50000
 1 ≤ u, v ≤ N
 the channels describe a tree
 1 ≤ sum of N over all test cases ≤ 250000
Example
Input: 2 4 10 25 15 40 1 2 1 2 3 3 1 4 4 7 24786 24640 17641 19735 8667 15790 5948 3 7 17108 7 6 4875 7 1 9317 1 2 8597 3 4 28200 1 5 22026 Output: 55 1148402043
Explanation
Example case 1: Chef can create cryptoexchanges on servers 2 and 4. Citizens on these servers receive Chefcoins immediately. The total time for Chefland's remaining citizens is the time it takes 15 citizens to move from server 3 to server 2 (3 · 15 = 45) plus the time it takes 10 citizens to move from server 1 to server 2 (1 · 10 = 10), so the optimal total time is 55.
Author:  mgch 
Tester:  wwwwodddd 
Editorial  https://discuss.codechef.com/problems/CTREE 
Tags  cook91, datastructure, dfs, graphtheory, hard, mgch, tree 
Date Added:  3022018 
Time Limit:  1 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. 