最佳训练基地（base）

题目描述

$\text{DAMON THRONE}$ 准备在一片训练区中建设一个新的训练基地。

训练区由 $n$ 个地点和 $n-1$ 条道路组成，任意两个地点之间都可以通过道路互相到达，并且不存在环。也就是说，这些地点和道路构成一棵树。

第 $i$ 个地点有 $c_i$ 名同学。第 $i$ 条道路连接地点 $u_i$ 和 $v_i$，道路长度为 $w_i$。

如果把训练基地建在地点 $x$，那么所有同学前往训练基地的总代价为：

其中 $dist(i,x)$ 表示地点 $i$ 到地点 $x$ 的树上最短距离。

请你选择一个地点建设训练基地，使所有同学前往基地的总代价最小。

如果有多个地点都能取得最小总代价，输出编号最小的地点。

输入格式

第一行包含一个整数 $n$，表示地点数量。

第二行包含 $n$ 个整数：

表示每个地点的同学数量。

接下来 $n-1$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示地点 $u_i$ 和地点 $v_i$ 之间有一条长度为 $w_i$ 的道路。

输出格式

输出一行，包含两个整数，分别表示：

• 最优建设地点编号；
• 最小总代价。

输入输出样例 #1

输入 #1

5
3 2 1 4 2
1 2 1
1 3 2
2 4 3
2 5 1

输出 #1

2 20

样例解释 #1

如果基地建在地点 $2$，总代价为：

可以证明没有其他地点的总代价更小，因此输出：$\text{2 20}$

输入输出样例 #2

输入 #2

4
1 1 1 1
1 2 1
2 3 1
3 4 1

输出 #2

2 4

样例解释 #2

如果基地建在地点 $2$，总代价为：

如果基地建在地点 $3$，总代价也为：

由于地点 $2$ 的编号更小，所以输出 $2$。

数据范围与约定

对于所有测试数据，保证：

保证输入的 $n-1$ 条边构成一棵树。

特殊性质 $\text{A}$：保证所有 $c_i=1$ 且所有 $w_i=1$。

特殊性质 $\text{B}$：保证所有 $c_i=1$。