City

Lucida occupies $n$ cities connected by $m$ undirected roads, and each road has a strength $k_i$. The enemy will attack to destroy these roads. When the enemy launches an attack with damage $x$, all roads with strength less than $x$ will be destroyed.

Now Lucida has $Q$ questions to ask you, how many pairs of cities are reachable to each other if the enemy launches an attack with damage $p_i$. City $x$ and city $y$ are reachable, which means that there is a path from $x$ to $y$, and every road's strength in that path is greater than or equal to $p_i$.

This problem contains multiple test cases.

The first line contains a single integer $T$ ($1\leq T \leq 10$).

Then $T$ test cases follow.

For each test case, the first line contains 3 integers $n, m, Q$ ($2 \leq n \leq 10^5$, $1 \leq m \leq 2 \times 10^5$, $1 \leq Q \leq 2 \times 10^5$), which represent the number of cities, the number of roads, and the number of queries.

The next $m$ lines, each line contains three integers $x, y, k$ ($1 \leq x, y \leq n$, $1 \leq k \leq 10^9$), which represent the road connecting city $x$ and city $y$, and the strength of this road is $k$.

The next $Q$ lines, each line contains an integer $p_i$ ($1 \leq p_i \leq 10^9$), asking how many pairs of cities are reachable to each other if the enemy launches an attack with damage $p_i$.

Output $\sum_{1}^{T} Q$ lines, each line contains an integer, representing the answer for each question.

1
5 5 3
1 2 2
2 3 3
3 4 1
4 5 1
5 1 3
3
2
1

2
6
10

“红旗杯”第十五届东北地区大学生程序设计竞赛