Description

Given a tree $T$, both vertices and edges have weights.

A simple path is a path that does not pass through any vertex more than once. It can be proved that the simple path between two nodes $u$ and $v$ is unique; we denote it by $P(u,v)$. The length of a path is the sum of the weights of all edges on it.

You have two sets $S$ and $G$.

At the beginning, you must choose one node as the current node and add it to the set $S$. Then you may perform any number of operations. One operation is as follows:

Suppose your current node is $u$. You may choose a node $v$ such that $v \neq u$, then update your current node to $v$, add node $v$ to the set $S$, and add the path $P(u,v)$ to the set $G$.

After you finish all operations, the profit you get is: the minimum of (the sum of vertex weights of all nodes in $S$) $\times$ (the sum of lengths of all paths in $G$). If $G$ is empty, we consider the value of the second term to be $0$.

Note that both $S$ and $G$ are sets, not multisets. This means that even if you add the same node to $S$ multiple times, it is counted only once when computing the vertex-weight sum.

Find the maximum possible profit.

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $a_1,a_2 \ldots a_n$, representing the vertex weights of these $n$ nodes.

The next $n - 1$ lines each contain three integers $u,v,w$, indicating that there is an edge of weight $w$ between $u$ and $v$.

Output Format

Output one integer, the maximum profit.

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

198

Hint

This problem uses bundled testdata.

For all data, it is guaranteed that $1 \leq n \leq 214748$, $0 \leq a_i \leq 10000$, and $1 \leq w \leq 10000$.

Sample #1 Explanation

The graph given in the first sample is as follows.

Translated by ChatGPT 5