题目背景

风暴席卷了见泷原市。

市气象局还未来得及建立起任何监测设施，要想确定风暴的状态，只能借助市内的风力计数据。而这项任务被交给了你——气象局新聘任的一名数据工程师。

题目描述

城市中有 $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
5 5 2
1 2 4 8 16
1 2 1
1 3 2
3 4 2
4 5 2
2 5 1

27

数据范围与提示

对所有数据：

• $\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$ 分，无额外限制

后记

在埋头调试的间隙，你抬头望了望窗外，迎面晃眼的阳光却让你一愣。

不知何时，风暴已经停息了。