B 道路（road）

TIME:2S
Memory:512M

题目描述

给出一张$n$个点，$m$条边的无向图。每个点有一个点权$a_i$，每条边有一个边权$b_i$。设这$m$条边组成的集合为$E$，对于一个边集$S$，定义其“导出点集”$nxt(S)=\{ x|∃_e \in S,x是e的一个端点 \}$ 。

再给出一个整数$k$ ，求$max_{|S| \le k} \sum_{x \in nxt(S)}a_x-\sum_{e \in S}b_e$ 。

换言之，就是选出一个不超过$k$条边的边集$S$ ，最大化（$nxt(S)$ 的点权和减去$S$内的边权和）。（边集可以为空）

从 graph.in 读入数据。

第一行一个整数$T$，表示数据组数；

对于每组数据：

第一行三个整数$n,m,k$；第二行$n$个整数，$a_{1...n}$ ，表示每个点的点权；接下来的$m$ 行，每行三个整数$x_i,y_i,b_i$，表示一条边的两端点和边权。

向 graph.out 输出答案。对于每组数据，输出一行一个整数，表示答案。

见下发文件。

对于10%的数据，保证图是一棵没有重边的树。

对于另外20%的数据，$n \le 15$ 。

对于另外30% 的数据，$a_i=1,b_i=0,k \le 8$ 。

对于所有数据，$T \le 3,1 \le n,m \le 100,1 \le k \le 10, 0 \le a_i,b_i \le 10^8,1 \le x_i,y_i \le n,x_i \neq y_i,$，给出的图没有自环，但可能有重边。