时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H所在的社区有 \(N\) 个居民点，其中第i个居民点居住着 \(s_i\) 个居民。居民点由 \(N-1\) 条双向道路连接，并且从任意一个居民点都能够到达另外一个居民点。道路i连接居民点 \(a_i\) 和 \(b_i\)，长度为 \(c_i\)。

　　区政府计划修建一所社区医院，在选择医院修建地点时，区长希望最大化方便的程度也就是最小化不方便程度。比如选择第 \(k\) 个居民点修建社区医院，它的不方便程度是其它居民点中每个人道医院所走的路程之和（比如居民点 \(i\) 到达居民点 \(j\) 的距离是 20，那么从i到j的总路程就是 \(s_i*20\)）。请你帮助市长找出最方便的社区医院地点。

【输入格式】

　　第一行一个整数 \(N\) 。
　　第二到 \(N+1\) 行，其中第 \(i+1\) 行有一个整数 \(s_i\)。
　　第 \(N+2\) 行到 \(2N\) 行,其中第 \(i+N+1\) 行为三个整数：\(a_i\),\(b_i\)和\(c_i\)。

【输出格式】

　　一行一个整数，表示最小的不方便值。

【输入输出样例1】

　Input

5 
1 
1 
0 
0 
2 
1 3 1 
2 3 2 
3 4 3 
4 5 3 

　Output

15

【样例1解释】

　　如果在3号居民点修建医院，则个社区居民到医院的不方便度为：
　　\(∙\) 1号居民点：1*1=1
　　\(∙\) 2号居民点：1*2=2
　　\(∙\) 3号居民点：0*0=0
　　\(∙\) 4号居民点：0*3=0
　　\(∙\) 5号居民点：2*(3+3)=12
　　\(∙\) 总不方便度为：1+2+0+0+12=15。

【输入输出样例2】

　Input

5
27
0
381
143
38
2 5 72
3 5 45
4 2 142
1 4 77 

　Output

47819

【数据限制】

　　- 对于 \(100\%\) 的数据，有 \(1≤ N≤ 105，1≤ai,bi≤N，0≤si,xi≤103\)。

【来源】

　　Mr.he