Spanning Tree#10754
Given a tree with vertices and n-1 edges. The -th edge connects vertices u_i and v_i, and has weight w_i. The -th vertex also has a value x_i.
Let f(a, b) — be the distance between vertices and plus x_a + x_b.
Consider a complete graph , where the weight of the edge between vertices and is f(a, b). Find the weight of the minimum spanning tree.
The first line contains a single integer (2 \leq n \leq 200\,000).
The second line contains integers x_1, x_2, \dots, x_n (1 \leq x_i \leq 10^9).
Each of the next n-1 lines contains three integers u_i, v_i and w_i (1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9).
Print a single integer — the answer to the problem.
Example 1
Example 2
Example 3