题目描述

某个国家有 $n$ 座城市，目前还没有建任何道路。第 $i$ 座城市有 $w_i$ 人口。还有 $n-1$ 条候选道路可以修建。第 $i$ 条道路如果被修建，将连接城市 $u_i$ 和 $v_i$，修建费用为 $s_i$。

如果把所有候选道路都修建起来，那么任意城市之间都可以互相到达。也就是说，这些候选道路构成一棵树。

接下来的 $k$ 天中，每天会发生如下事件：在第 $i$ 天，选择一座城市 $c_i$，并选择两条尚未修建且都连接 $c_i$ 与其他城市的不同道路。然后修建这两条道路，并支付费用，费用等于这两条道路修建费用之和。城市 $c_i$ 会被认为是第 $i$ 天的中心城市。

$k$ 天后，每个至少作为中心城市出现过一次的城市会产生收益，收益等于该城市的人口数量。

定义收益值 benefit 为：

请你求出最大可能的收益值。

输入格式

第一行包含三个整数 $n,k,t$（$3 \le n \le 200000$，$1 \le k \le \frac{n-1}{2}$，$0 \le t \le 1$），分别表示城市数、要修建的道路对数，以及是否需要输出具体方案。若 $t=1$，则需要输出修建方案；若 $t=0$，则只需要输出最大收益值。

第二行包含 $n$ 个整数 $w_1,w_2,\dots,w_n$（$1 \le w_i \le 10^8$），表示每座城市的人口。

接下来 $n-1$ 行，每行包含三个整数 $u_i,v_i,s_i$（$1 \le u_i,v_i \le n$，$1 \le s_i \le 10^8$），表示第 $i$ 条候选道路连接的两座城市和修建费用。

保证候选道路构成一棵树，并且存在满足条件的方式修建 $k$ 对道路。

输出格式

第一行输出一个整数，表示修建恰好 $k$ 对道路后可以得到的最大收益值。

如果 $t=1$，接下来输出 $k$ 行，每行包含三个整数 $c_i,x_i,y_i$（$1 \le c_i,x_i,y_i \le n$），表示第 $i$ 天修建道路 $(c_i,x_i)$ 和 $(c_i,y_i)$，中心城市为 $c_i$。

如果存在多种最优方案，输出任意一种。

样例 #1

样例输入 #1

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

样例输出 #1

-3
5 6 1
2 4 1

样例 #2

样例输入 #2

8 3 0
4 5 1 2 3 1 3 5
2 1 15
7 1 5
4 8 1
8 5 2
7 8 1
6 7 5
3 7 7

样例输出 #2

-13

样例解释

第一个样例中，最优方案中修建的道路如下，同一对道路在原题图中用相同颜色标记：

第一个样例的最优建路方案。

修建道路的总费用为 $2+4+1+3=10$。修建完成后，城市 $2$ 和 $5$ 产生收益，分别为 $2$ 和 $5$。因此收益值为：

可以证明无法得到更好的答案。

第二个样例中，最优方案如下：

第二个样例的最优建路方案。

修建道路的总费用为 $5+1+2+1+5+7=21$。修建完成后，城市 $7$ 和 $8$ 产生收益，分别为 $3$ 和 $5$。因此收益值为：

可以证明无法得到更好的答案。

评分方式

测试数据包含 7 个测试组。只有通过该组以及若干指定的前置测试组，才能获得该组分数。Offline-testing 表示该组结果只会在比赛结束后公布。