题目背景
风暴席卷了见泷原市。
市气象局还未来得及建立起任何监测设施，要想确定风暴的状态，只能借助市内的风力计数据。而这项任务被交给了你——气象局新聘任的一名数据工程师。
题目描述
城市中有 $M$ 条主要街道，它们连接着 $N$ 个路口。在每个路口处都有一个风力计，其中路口 $i$ 处的风力计示数为 $v_i$ ，示数越大表示风力越强。
在街道中可能出现“狭管效应”，即气流经过狭窄的区域时压强降低、流速升高的现象。这会导致穿过该街道的风速提高，从而使得该街道连接的路口处风力计示数相比真实值偏大。第 $i$ 条街道的该效应强度为 $e_i$ 。
为了确定风暴中心地带的范围，你需要找到一个由不超过 $K$ 条街道（可以是 $0$ 条，另外注意不能重复选择一条街道）组成的集合 $S$ ，以最大化： $$ \sum\limits_{x\in I(S)} v_x -\sum\limits_{y\in S} e_y \tag{1} $$ 其中 $I(S)$ 表示所有与 $S$ 中至少一条街道相连的路口构成的集合。
如果一个路口与超过一条 $S$ 中的街道相连，它也只会被算入一次。气象专家猜测风暴的外围可能存在多个较小的气旋，从而可能存在多个独立的风暴中心，因此你选出的街道集合不一定连通。
请你尽快完成任务，气象局能否采取下一步行动取决于你的表现。
输入格式
第一行一个正整数 $T$ ，表示测试点个数。接下来对每个测试点：
- 第一行三个正整数 $N,M,K$ ，分别表示路口个数、街道条数、选取街道数量的上限。路口按 $1$ 到 $N$ 标号，街道按 $1$ 到 $M$ 标号。
- 第二行 $N$ 个非负整数，表示 $v_1,v_2,\cdots,v_N$ 。
- 接下来 $M$ 行，其中的第 $i$ 行有三个整数 $a_i,b_i,e_i$ ，表示街道 $i$ 连接路口 $a_i$ 与 $b_i$ ，其狭管效应强度为 $e_i$ 。
输出格式
对每个测试点输出一行一个整数，表示 $(1)$ 式的最大值。
样例数据
样例 1 输入
1 5 5 2 1 2 4 8 16 1 2 1 1 3 2 3 4 2 4 5 2 2 5 1
样例 1 输出
27
样例 1 解释
集合 $S$ 应包含街道 $(2,5)$ 和街道 $(3,4)$ ，其 $e_i$ 值之和为 $3$ 。此时 $I(S)$ 包含结点 $2,3,4,5$ ，其 $v_i$ 值之和为 $30$ 。
子任务
对所有数据：
- $\sum 2^K(N+M)\leq 10^6$ ，这里的求和号表示对一组数据中所有测试点求和。
- $\space 1\leq T\leq 5$
- $\space 1\leq N,M,K$
- $\space 0\leq e_i,v_i\leq 10^8$
- $\space 1\leq a_i,b_i\leq N$
- 所有路口和街道所构成的无向图没有自环，但可以有重边、可以不连通、可以有孤立点。
- 保证答案不超过 $2\cdot 10^9$ 。
子任务 $1$：$30$ 分，$\sum (N+M)\leq 1500$
子任务 $2$：$30$ 分，$K\leq 9$
子任务 $3$：$40$ 分，无额外限制
后记
在埋头调试的间隙，你抬头望了望窗外，迎面晃眼的阳光却让你一愣。
不知何时，风暴已经停息了。