5.周年纪念日

题目描述

给定一张有$n$个点和$m$条被破坏的道路的无向图，一开始我们需要修建道路满足$n$个点连通并且最大边权最小。输出最大边权以及所有边权和。其次，第$i$个点有$P_{i}$个居民，一个居民走$1$单位长度的路径会产生$1$的不高兴度，现在要求找一个点使得所有居民的不高兴度之和最小。输出这个点及所有人的不高兴度之和。

输入格式

第一行包含两个整数$n$和$m$，表示有$n$个城市，$m$条被破坏的道路；

接下来$n$行，每行包含一个整数$P_{i}$，表示城市$i$的居民人数；

接下来$m$行，每行三个整数$A_{i}$，$B_{i}$，$L_{i}$，表示点$A_{i}$和点$B_{i}$之间有一条长度为$L_{i}$的被破坏道路。

注意：两个城市之间可能会有多条道路。

输出格式

输出数据包含两行。

第一行两个整数$C$，$T$（用一个空格隔开），表示修建道路的最大边权和所有边权和；

第二行两个整数$U$，$H$（用一个空格隔开），表示晚会的地点（如果有多个地点满足条件，输出编号最小的那个城市）和相应地点所有人的不高兴度之和。

数据范围与提示

对于$100\%$的数据，$1 \leq n \leq 10^{5}$，$1 \leq m \leq 2 \times 10^{5}$，$1 \leq L \leq 10^{6}$，$1 \leq P_{i} \leq 10^{6}$，$1 \leq A_{i},B_{i} \leq n$，$A_{i} \neq B_{i}$。

输入数据保证只存在一种合法的修建方案，且所有运算结果在$64$位有符号整数以内。

样例

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

11 5 
5 29

说明

合法的修建方案如下图（相邻城市之间的距离和每个城市的人数见样例）：

依次选取每个点做晚会地址的不开心度之和如下表：

因此需要选取城市$5$作为晚会地址，不高兴度之和为$29$。