题目背景

小 M 很喜欢草莓。

草莓可以抽象为一棵树 $T$。我也不知道为什么可以，但草莓甚至可以飞，抽象成一棵树想必问题也不大吧。

题目描述

给定一棵树 $T$，点和边均有权值。

一条简单路径是一条不重复经过任意一个点的路径。可以证明，两个节点 $u$ 和 $v$ 之间的简单路径是唯一的，我们将其记为 $P(u,v)$。一条路径的长度是它所包含的所有边的权值和。

你有两个集合 $S$ 和 $G$。

在一开始，你必须选择一个点作为 当前点 并且将其加入集合 $S$。接下来可以进行任意次操作，一次操作的形式如下：

假设你的 当前点 为 $u$，你可以选择一个节点 $v$，使得 $v \neq u$，然后将你的 当前点 更新为 $v$，并且将点 $v$ 加入集合 $S$，将路径 $P(u,v)$ 加入集合 $G$。

在你进行完所有操作之后，你得到的收益为 $S$ 中所有点的点权和 $\times$ $G$ 中所有路径的长度的最小值。如果 $G$ 为空，我们认为第二项的值为 $0$。

注意 $S$ 和 $G$ 都是 不可重集，这意味着，即使你多次将某个点加入集合 $S$，最终在计算点权时，也只会被计算一次。

求得到的收益的最大值。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数 $a_1,a_2 \ldots a_n$，表示这 $n$ 个节点的点权。

接下来 $n - 1$ 行，每行三个整数 $u,v,w$，表示 $u$ 到 $v$ 有一条权值为 $w$ 的边。

输出格式

输出一个整数，所求最大收益。

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

198

提示

本题采用 捆绑测试。

对于所有数据，保证 $1 \leq n \leq 214748, 0 \leq a_i \leq 10000$，$1 \leq w \leq 10000$。

样例 #1 解释

第一组样例给定的图如下。