409805: GYM103765 J 在一起

ACMer分布在全国的n个不同的城市，编号为。任意两个城市都连通，且只有唯一的一条通路。

你们决定来一次全体聚会，请选出一个城市作为聚会地，使得所有人的距离和最小。

第一行是一个整数T (1 ≤ T ≤ 10)，表示样例的个数，所有测试数据样例总数不超过100。

每个样例的第一行是一个整数n (1 ≤ n ≤ 10000)。

第二行是n个整数，表示第i个城市里的ACMer的人数a_i (1 ≤ a_i ≤ 100)。

从第三行起的n - 1行，每行三个整数u, v, w,  (1 ≤ u < v ≤ n), 1 ≤ w ≤ 100，表示城市u和v之间有一条路，距离为w。

依次输出每个样例的结果，为两个整数，第一个为聚会城市的编号，第二个为所有人的距离和，两者之间用一个空格隔开。

如果存在多个符合条件的城市，取编号最小的。

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

2 34

选1号城市作为聚会地，距离和为(2 + 3)·1 + (4 + 5 + 6)·2 = 35。

选2号城市作为聚会地，距离和为(1 + 4 + 5)·1 + 3·2 + 6·3 = 34。

选3号城市作为聚会地，距离和为(1 + 7)·1 + 2·2 + (4 + 5)·3 = 39。

选4号城市作为聚会地，距离和为2·1 + (1 + 5)·2 + 3·3 + 6·4 = 47。

选5号城市作为聚会地，距离和为2·1 + (1 + 4)·2 + 3·3 + 6·4 = 45。

选6号城市作为聚会地，距离和为3·1 + 1·2 + 2·3 + (4 + 5)·4 = 47。