题目背景

给一棵树，边有边权，节点 $i$ 最多保留 $d_i$ 条邻边。求保留的边边权之和最大多少？

题目描述

给一棵有 $n$ 个顶点的有权树。

考虑从 $n-1$ 条边中选择一些边。对于每个节点 $i$ ，最多有 $d_i$ 条邻边被选择。

求所选边权的最大总权重。

输入格式

第一行输入一个整数 $n$ ( $1 ≤ n ≤ 3\times 10^5$ ) 表示树上顶点的数量。

第二行输入 $n$ 个整数，表示 $d_i$ 。

接下来的 $n-1$ 行分别包含三个整数： $u_i,v_i,w_i$ 描述一条树上的边。

输出格式

输出最大总权重。

输入输出样例 #1

输入 #1

7
1 2 1 0 2 1 1
1 2 8
2 3 9
2 4 10
2 5 -3
5 6 8
5 7 3

输出 #1

28

输入输出样例 #2

输入 #2

20
0 2 0 1 2 1 0 0 3 0 1 1 1 1 0 0 3 0 1 2
4 9 583
4 6 -431
5 9 325
17 6 131
17 2 -520
2 16 696
5 7 662
17 15 845
7 8 307
13 7 849
9 19 242
20 6 909
7 11 -775
17 18 557
14 20 95
18 10 646
4 3 -168
1 3 -917
11 12 30

输出 #2

2184

说明/提示

• $2 \leq n \leq 3 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• $-10^9 \leq w_i \leq 10^9$
• $d_i$ 是一个非负整数，且不超过顶点 $i$ 的阶数。

对于 $30 \%$ 的数据： $1\le n \le 20$

对于 $60 \%$ 的数据： $1\le n \le 2000$

对于 $100 \%$ 的数据： $1\le n \le 3\times 10^5$