题目描述

Tree 国有 $T$ 个省，每个省的省内道路组成一棵 Tree。这天 Tree 国的国王得到了神明的赐福：在 Tree 国开设“银行”吧！Tree 国的商人们会在“银行”的帮助下给你带来源源不尽的金银财宝！不过目前 Tree 国国库不是很富裕，Tree 国只能在每个省开设两家银行。

既然如此，那就最大化银行的性价比吧！假设 Tree 国某个省有 $n$ 座城市，城市之间的道路当然满足 Tree 的约束，通行某条道路需要花费相应的时间。该省第 $i$ 个城市生活着 $a_i$ 个居民，当某位居民需要银行的服务时，该居民自然会去离自己城市最近的银行。可想而知，在未来该省两家银行开业的那一天，该省所有居民都会去离家最近的银行办卡，因此该省银行的性价比就定义为该省所有居民去往银行需要花费的时间之和。花费时间和越少性价比越高。

那么对于每个省，最优的银行建设方案是什么呢？

输入格式

第一行一个正整数 $T$，表示 Tree 国的省份数量

对于每个省：

• 第一行一个正整数 $n$，表示该省有 $n$ 个城镇
• 第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个城镇的居民数
• 接下来 $n-1$ 行，每行三个正整数 $u, v, w$，表示城镇 $u$ 和城镇 $v$ 之间有一条道路，通行该道路需要花费 $w$ 的时间

输出格式

对于每个省，输出一行一个正整数，表示该省最优的银行建设方案中，所有居民去往银行需要花费的时间之和

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

59
128

样例2

d.in
d.out

数据范围与提示

对于所有数据，满足 $2 \leq n \leq 10^5, 1 \leq a_i, w \leq 5 \times 10^4, 1 \leq u, v \leq n, 2 \leq \sum n \leq 5 \times 10^5$。

每个省的省内道路保证是一棵树

• 特殊性质 A：保证树的形态是一条链。