This is the easy version of the problem. The changes in this version are highlighted in bold characters.
Yugandhar have an undirected graph containing $$$n$$$ nodes numbered $$$1,2,....,n$$$. Initially there are $$$0$$$ edges i.e., there are total $$$n$$$ connected components in the graph. He has a freedom to add exactly $$$k$$$ undirected edges in this graph, each edge can be added between $$$u$$$ and $$$v$$$ if and only if $$$v$$$ = $$$u+1$$$. Note that he can add multiple edges between two nodes.
After giving this graph to wuhudsm, he will observe the following $$$m$$$ requirements and reward him coins :
So Please tell him the optimal way to select these $$$k$$$ edges to get maximum number of coins.
Aditionally, help him for $$$q$$$ queries.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of test case contains three integers $$$n,m,q$$$ ($$$2 \le n \le \bf{2 \cdot 10^3}$$$, $$$1 \le m \le \bf{2 \cdot 10^3}$$$, $$$1 \le q \le 10^6$$$) — the number of nodes in graph, the number of requirements and the number of queries.
Next $$$m$$$ lines of each test case contains three space separated integers $$$x_{i}, y_{i}, c_{i}$$$ ($$$1 \le x_{i}, y_{i} \le n$$$, $$$x_{i} ≠ y_{i}$$$, $$$1 \le c_{i} \le 10^9$$$).
Next $$$q$$$ lines of each test case contains a single integer $$$k_{i}$$$ ($$$1 \le k_{i} \le 10^9$$$) — the total number of edges needed to add in graph.
It is guaranteed that the sum of $$$n$$$ and sum of $$$m$$$ over all test cases doesn't exceed $$$\bf{2 \cdot 10^3}$$$.
It is guaranteed that the sum of $$$q$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case print $$$q$$$ integers — the maximum number of coins he can get if he choose exactly $$$k_{i}$$$ edges optimally.
34 2 23 4 31 3 2135 3 33 4 23 1 52 5 102166 5 41 2 13 2 13 4 15 4 26 5 134810
3 5 5 2 17 4 5 6 6
