AT_abc409_e [ABC409E] Pair Annihilation

You are given a tree with $ N $ vertices. The vertices are numbered $ 1,2,\dots,N $ , and the edges are numbered $ 1,2,\dots,N-1 $ . Edge $ j $ bidirectionally connects vertices $ u_j $ and $ v_j $ and has weight $ w_j $ . Also, vertex $ i $ is given an integer $ x_i $ . If $ x_i > 0 $ , then $ x_i $ positrons are placed at vertex $ i $ . If $ x_i < 0 $ , then $ -x_i $ electrons are placed at vertex $ i $ . If $ x_i=0 $ , then nothing is placed at vertex $ i $ . Here, it is guaranteed that $ \sum_{i=1}^N x_i = 0 $ . Moving one positron or electron along edge $ j $ costs energy $ w_j $ . Also, when a positron and an electron are at the same vertex, they annihilate each other in equal numbers. Find the minimum energy required to annihilate all positrons and electrons.

The input is given from Standard Input in the following format: > $ N $ $ x_1 $ $ x_2 $ $ \dots $ $ x_N $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ w_{N-1} $

Output the answer.

### Sample Explanation 1 Initially, $ x=(x_1,x_2,x_3,x_4)=(-3,+2,+2,-1) $ . By operating as follows, all positrons and electrons can be annihilated with energy $ 9 $ : - Move one electron at vertex $ 1 $ to vertex $ 2 $ . This costs energy $ 2 $ , and $ x=(-2,+1,+2,-1) $ . - Move one positron at vertex $ 2 $ to vertex $ 1 $ . This costs energy $ 2 $ , and $ x=(-1,0,+2,-1) $ . - Move one electron at vertex $ 4 $ to vertex $ 1 $ . This costs energy $ 3 $ , and $ x=(-2,0,+2,0) $ . - Move one electron at vertex $ 1 $ to vertex $ 3 $ . This costs energy $ 1 $ , and $ x=(-1,0,+1,0) $ . - Move one electron at vertex $ 1 $ to vertex $ 3 $ . This costs energy $ 1 $ , and $ x=(0,0,0,0) $ . It is impossible to annihilate all positrons and electrons with energy $ 8 $ or less, so the answer is $ 9 $ . ### Sample Explanation 2 The condition may already be satisfied from the beginning. ### Constraints - $ 2 \leq N \leq 10^5 $ - $ |x_i| \leq 10^4 $ - $ \sum_{i=1}^N x_i = 0 $ - $ 1 \leq u_j < v_j \leq N $ - $ 0 \leq w_j \leq 10^4 $ - The given graph is a tree. - All input values are integers.