qsgg and Money
题号：NC253374
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一棵含有 n 个节点的树。

每个节点都有一个加油站，该节点加油站每升油耗费 c_i 元，经过一条边耗费 h_i 升油。

定义函数 F(u,v)，初始车剩余油量为 0 升，从 u 点出发到达 v 点的简单路径所花费的最少的钱。若 u=v，F(u,v)=0。

现在你想知道  \sum \limits_{u=1}^{n}\sum \limits_{v=1}^{n}F(u,v)。

注意：若当前车剩余油量小于该边耗费油量，则无法通过该边。且车剩余油量无上限。

输入描述:

输入共 n+1 行。
第一行一个整数表示 n\ (1≤n≤2\times 10^5)，n 表示节点个数。
第二行 n 个整数，c_i 表示在 i 号节点加油站每升油耗费 c_i 元 (1≤c_i≤50)。
接下来 n-1 行，每行三个整数 u_i,v_i,h_i，表示第 i 条边连接 u_i,v_i，经过该边耗费 h_i 升油 (1≤u_i,v_i≤n,1≤h_i≤100)。

输出描述:

输出一个整数，表示 \sum \limits_{u=1}^{n}\sum \limits_{v=1}^{n}F(u,v) 。
示例1

输入

复制 
5
1 1 4 5 1
1 2 4
1 3 1
1 5 9
3 4 1

输出

复制 
161

说明

例如，从 4 号节点到 2 号节点的最少用钱方式是：先在 4 号节点加 1 升油到达 3 号节点，再在 3 号节点加 1 升油到达 1 号节点，最后在 1 号节点加 4 升油到达 2 号节点，F(4,2) = 13。