描述

话说宁波市的中小学生在镇海中学参加计算机程序设计比赛，比赛之余，他们在镇海中学的各个景点参观。镇海中学共有n个景点，每个景点均有若干学生正在参观。这n个景点以自然数1至n编号，每两个景点的编号均不同。每两个景点之间有且只有一条路径。选择哪个景点集中所有的学生，才能使所有学生走过的路径之和最小呢？

格式

输入格式

第一行只有一个正整数n，表示景点数。

第二行有n个1至1000间的整数，这n个整数间互相以一个空格分隔。其中第i个整数表示第i个景点处的学生数。

第三行至第n+1，每行有三个整数i,j,k，表示景点i和景点j之间有一条长为k的路径直接连接。其中i<>j，1≤i≤n, 1≤j≤n；1≤k≤1000。

输出格式

有二行：
第一行只有一个整数i，表示在第i个景点处集中时，所有学生走过的路径之和最短。

第二行也只有一个整数，表示所有学生走过的路径之和的最小值。

样例1

样例输入1

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

样例输出1

1
43

限制

1s

提示

【样例说明】
如上图所示，景点1有3个学生，景点2有2个学生，景点3有4个学生，景点4有1个学生；景点1与景点2间距离5，景点1与景点3间距离6，景点2与景点4间距离4。此时，选择在景点1处集中时，所有学生走过的路径之和为最小，该最小值为43。

【数据限制】
所有的数据均随机生成，且满足：
30%的数据，1≤n≤200。

60%的数据，1≤n≤3000。

100%的数据，1≤n≤100000。

来源

宁波市第23届中小学生计算机程序设计竞赛决赛试题（高中组）第四题