题目描述

给定一棵有 $N$ 个顶点的树。每个顶点 $u$ 有权值 $w_u$，每条边 $(a_i,b_i)$ 有长度 $l_i$。

我们知道，树的重心会最小化到所有顶点距离之和；但那样就太简单了。

请找到一个顶点 $x$，使下面的和最小：

其中 $d(u,v)$ 表示顶点 $u$ 与顶点 $v$ 之间的距离，即路径上边长之和。

若有多个顶点都能使上述和最小，输出编号最小的顶点。

输入格式

输入格式如下：

N
w_1 w_2 ... w_N
a_1 b_1 l_1
...
a_{N-1} b_{N-1} l_{N-1}

输出格式

输出一个整数，表示使上述和最小的顶点 $x$。

数据范围

• $1\le N\le 2\times 10^5$
• $1\le l_i\le 1000$
• $0\le w_u\le 10^8$

子任务

样例

输入

3
1 5 1
1 3 42
1 2 42

输出

2

样例解释

当 $x=2$ 时，上述和最小，约为 $1042.06382$。