AT_abc409_e [ABC409E] Pair Annihilation

$ N $ 頂点の木が与えられます。頂点には $ 1,2,\dots,N $ の番号が、辺には $ 1,2,\dots,N-1 $ の番号がついています。辺 $ j $ は頂点 $ u_j,v_j $ を双方向に結び、重み $ w_j $ を持ちます。また、頂点 $ i $ には整数 $ x_i $ が与えられており、 $ x_i > 0 $ なら $ x_i $ 個の陽電子が、 $ x_i < 0 $ なら $ -x_i $ 個の電子が頂点 $ i $ に置かれています。 $ x_i=0 $ ならば頂点 $ i $ には何もありません。ここで、 $ \sum_{i=1}^N x_i = 0 $ が保証されます。 陽電子または電子 $ 1 $ 個を辺 $ j $ に沿って動かすと、エネルギー $ w_j $ がかかります。また、陽電子と電子が同じ頂点にあるとき、それらは同じ数だけ打ち消し合って消滅します。 すべての陽電子と電子を消滅させるために必要なエネルギーの最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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} $

答えを出力せよ。

### Sample Explanation 1 はじめ、 $ x=(x_1,x_2,x_3,x_4)=(-3,+2,+2,-1) $ です。 次のように操作することで、エネルギー $ 9 $ ですべての陽電子と電子を消滅させることができます。 - 頂点 $ 1 $ にある電子を $ 1 $ つ、頂点 $ 2 $ に移動させる。エネルギー $ 2 $ がかかり、 $ x=(-2,+1,+2,-1) $ となる。 - 頂点 $ 2 $ にある陽電子を $ 1 $ つ、頂点 $ 1 $ に移動させる。エネルギー $ 2 $ がかかり、 $ x=(-1,0,+2,-1) $ となる。 - 頂点 $ 4 $ にある電子を $ 1 $ つ、頂点 $ 1 $ に移動させる。エネルギー $ 3 $ がかかり、 $ x=(-2,0,+2,0) $ となる。 - 頂点 $ 1 $ にある電子を $ 1 $ つ、頂点 $ 3 $ に移動させる。エネルギー $ 1 $ がかかり、 $ x=(-1,0,+1,0) $ となる。 - 頂点 $ 1 $ にある電子を $ 1 $ つ、頂点 $ 3 $ に移動させる。エネルギー $ 1 $ がかかり、 $ x=(0,0,0,0) $ となる。 $ 8 $ 以下のエネルギーですべての陽電子と電子を消滅させることはできないため、答えは $ 9 $ です。 ### Sample Explanation 2 はじめから条件が満たされている場合もあります。 ### 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 $ - 与えられるグラフは木である - 入力はすべて整数