题目描述

一个国家有 $n$ 座城市和 $n-1$ 条道路。第 $i$ 座城市有商业价值 $c_i$；第 $j$ 条道路连接城市 $u_j,v_j$，有建设代价 $w_j$。保证 $n$ 座城市被连成了一棵树。

你可以进行 $k$ 次城市建设，每次可以选择一座城市（可以之前被建设过）和两条和这座城市相邻的，没有被建设的道路建设。

$k$ 次城市结束后，如果城市 $i$ 被至少建设过一次，则会产生 $c_i$ 的收益；如果道路 $j$ 被建设过，则会产生 $w_j$ 的代价。求最大收益（可能为负）。

保证有解，即至少存在一种进行 $k$ 次城市建设的方案。

输入格式

第一行三个整数 $n,k,t$。如果 $t=0$ 则不需要构造方案，否则需要构造方案。

第二行 $n$ 个整数 $c_1,c_2,\cdots,c_n$。

接下来 $n-1$ 行，其中第 $j$ 行三个整数 $u_j,v_j,w_j$。

输出格式

第一行输出一个整数表示最大收益。

如果 $t=1$，则还需要输出 $k$ 行，第 $i$ 行三个整数 $u_i,v1_i,v2_i$，表示选择了城市 $u_i$ 和道路 $(u_i,v1_i),(u_i,v2_i)$。

样例

样例输入 #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

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

g++ -o check check.cpp -O2 -std=c++14

./check <input-file> <output-file> <answer-file>

check <input-file> <output-file> <answer-file>