6603: Weighted Beautiful Tree

A tree is a connected graph with n nodes and n−1 edges.

You are given a weighted tree with n nodes. The i-th node has a weight of wni and a cost of ci. The i-th edge connecting node ui and vi has a weight of wei. The edge is called beautiful if and only if it meets min(wnui,wnvi)≤wei≤max(wnui,wnvi).

You can do the following operation several times.

• Choose a node u, then change its weight wnu into wn′u. The total cost adds cu|wnu−wn′u|.

What is the minimum total cost to make all edges beautiful?

The first line contains an integer T, denoting the number of test cases.

For each test case, the input format is as follows:

| n | | | | |
|-----------|-----------|------------|----------|--------|
| c1 | c2 | c3 | … | cn |
| wn1 | wn2 | wn3 | … | wnn |
| u1 | v1 | we1 | | |
| u2 | v2 | we2 | | |
| ⋮ | ⋮ | ⋮ | | |
| un−1 | vn−1 | wen−1 | | |

It is guaranteed that:

• 1≤T≤103
• 1≤n≤105, ∑n≤106
• 1≤ci,wni,wei≤106

For each test case, output an integer in a single line, denoting the minimum total cost.