题目背景

嵐が見滝原市を襲った。

市気象局はまだ観測施設を設置できておらず、嵐の状態を特定するには市内の風力計のデータに頼るしかない。この任務は、気象局に新しく採用されたデータエンジニアであるあなたに託された。

题目描述

市内には $N$ 個の交差点と、それらを結ぶ $M$ 本の主要な通りがある。各交差点には風力計が設置されており、交差点 $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$ 内の複数の通りに接続されている場合でも、その交差点は一度だけカウントされる。気象専門家は、嵐の周辺部には複数の小さなサイクロンが存在する可能性があり、したがって複数の独立した嵐の中心が存在し得るため、選択する通りの集合 $S$ は連結である必要はないと推測している。

気象局が次の行動をとれるかどうかはあなたの成果にかかっている。早急に任務を完了せよ。

入力

最初の行にテストケースの数 $T$ が与えられる。各テストケースについて以下の通りである。

• 第1行に3つの正整数 $N, M, K$ が与えられる。それぞれ交差点の数、通りの数、選択できる通りの上限数を表す。交差点には $1$ から $N$ までの番号が、通りには $1$ から $M$ までの番号が付けられている。
• 第2行に $N$ 個の非負整数が与えられ、それぞれ $v_1, v_2, \cdots, v_N$ を表す。
• 続く $M$ 行の各行には3つの整数 $a_i, b_i, e_i$ が与えられ、通り $i$ が交差点 $a_i$ と $b_i$ を結び、その狭管効果の強度が $e_i$ であることを表す。

出力

各テストケースについて、式 $(1)$ の最大値を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$ （ここで和は、1つのテストケース群に含まれるすべてのテストケースに対する合計を表す）
• $1\leq T\leq 5$
• $1\leq N, M, K$
• $0\leq e_i, v_i\leq 10^8$
• $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$ 点、追加の制約なし

後記

デバッグに没頭する合間に窓の外を見上げると、差し込む眩しい日差しに思わず立ち止まった。

いつの間にか、嵐は止んでいた。