基站选址

题目背景

某山区的村庄之间由公路连成一片网络。任意两座村庄之间有且仅有一条通路（也就是说，村庄与公路构成一棵树）。通信公司打算在其中一座村庄修建基站，让所有村庄都能收到信号。修在村庄 $u$ 时，村庄 $v$ 的居民需要沿着唯一通路赶到 $u$，公司的建设成本与“居民人数乘以路程”的总和有关。公司想选一个成本最低的位置。

题目描述

给定一棵 $n$ 个结点的树，结点编号 $1$ 到 $n$，第 $i$ 个结点上有 $p_i$ 名居民。

第 $i$ 条公路连接结点 $u_i$ 与 $v_i$，长度为 $w_i$ 公里。由于任意两点之间有唯一通路，可以定义 $\operatorname{dist}(u, v)$ 为结点 $u$ 与结点 $v$ 之间通路上所有公路长度之和。

如果在结点 $u$ 修建基站，那么建设成本为

$$\sum_{v=1}^{n} p_v \cdot \operatorname{dist}(u, v) .$$

请你求出所有候选位置中最小的建设成本，以及达到这个最小成本的编号最小的结点编号。

输入格式

从标准输入读入数据。

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_1, p_2, \dots, p_n$。

接下来 $n-1$ 行，每行三个整数 $u_i, v_i, w_i$，描述一条公路。保证给出的图是一棵树。

输出格式

输出到标准输出。

输出一行两个整数，用一个空格隔开：最小的建设成本，以及取到该成本的最小结点编号。

样例 1 输入

3
1 1 1
1 2 3
2 3 5

样例 1 输出

8 2

样例 1 解释

修在结点 $1$：$0 + 3 + 8 = 11$；修在结点 $2$：$3 + 0 + 5 = 8$；修在结点 $3$：$8 + 5 + 0 = 13$。最小成本是 $8$，对应唯一的结点 $2$。

样例 2 输入

2
1 1
1 2 7

样例 2 输出

7 1

样例 2 解释

修在两个结点上的成本都是 $7$，因此选择编号较小的结点 $1$。

数据范围

测试点编号	$n \le$	特殊性质
$1 \sim 3$	$2000$	无
$4 \sim 6$	$10^5$	树是一条链（对每个 $1 \le i < n$ 都有一条边连接 $i$ 与 $i+1$）
$7 \sim 10$		无

对全部测试数据，保证 $1 \le n \le 10^5$，$1 \le p_i \le 1000$，$1 \le w_i \le 10^4$。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。