你現在有一棵 \(n(2\leq n\leq {10}^6)\) 個點的樹，每條邊可能會有不同的權重 \(w(1\leq w\leq {10}^9)\) ，

一開始每個點 \(v(1\leq v\leq n)\) 我們會塗上一個顏色 \(color(v) (1\leq color(v)\leq{10}^9)\) ，

我們定義 \(dis(i,j)\) 為「點 \(i\) 到點 \(j\) 所經過的唯一路徑的權重總和」 \((i\neq j)\) ，請輸出 \(\mathop{max}\limits_{1\leq i, j\leq n, color(i)=color(j)}{\{dis(i,j)\}}\) 的值。

Input

第一行只有一個數字 \(n\) 。 \((2\leq n\leq {10}^6)\)

第二行有 \(n\) 個數字 \(color(1), color(2), \dots, color(n)\) ，以空格間隔。 \((\forall 1\leq i\leq n, 1\leq color(i)\leq {10}^9)\)

第三行開始的 \(n-1\) 行，每行有三個數字 \(u, v, w\) （以空格間隔），代表點 \(u, v\) 之間有一條邊權為 \(w\) 的邊。 \((1\leq u, v\leq n, u\neq v, 1\leq w\leq {10}^9)\)

Output

請輸出 \(\mathop{max}\limits_{1\leq i, j\leq n, color(i)=color(j)}{\{dis(i,j)\}}\) 的值。

Constraints

第 \(1\) 組測資， \(n\leq 5000\) 。 \(~~(27\%)\)

第 \(2\) 組測資， \(n\leq 2\cdot {10}^5\) 。 \((60\%)\)

第 \(3\) 組測資，無特別限制。 \(~~(13\%)\)

Sample Input 1

7
1 1 2 2 3 2 3
3 4 2
4 2 28
2 1 22
1 6 7
4 5 18
6 7 13

Sample Output 1

88

Sample Input 2

3
1 3 2
2 3 2
2 1 8

Sample Output 2

0