This is the hard version of the problem. In the three versions, the constraints on $$$n$$$ and $$$m$$$ are different. You can make hacks only if all the versions of the problem are solved.

Pak Chanek is setting up internet connections for the village of Khuntien. The village can be represented as a connected simple graph with $$$n$$$ houses and $$$m$$$ internet cables connecting house $$$u_i$$$ and house $$$v_i$$$, each with a latency of $$$w_i$$$.

There are $$$p$$$ houses that require internet. Pak Chanek can install servers in at most $$$k$$$ of the houses. The houses that need internet will then be connected to one of the servers. However, since each cable has its latency, the latency experienced by house $$$s_i$$$ requiring internet will be the maximum latency of the cables between that house and the server it is connected to.

For each $$$k = 1,2,\ldots,n$$$, help Pak Chanek determine the minimum total latency that can be achieved for all the houses requiring internet.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2000$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$p$$$ ($$$2 \le n \le 5000$$$; $$$n-1 \le m \le 5000$$$; $$$1 \le p \le n$$$) — the number of houses, the number of cables, and the number of houses that need internet.

The second line of each test case contains $$$p$$$ integers $$$s_1, s_2, \ldots, s_p$$$ ($$$1 \le s_i \le n$$$) — the houses that need internet. It is guaranteed that all elements of $$$s$$$ are distinct.

The $$$i$$$-th of the next $$$m$$$ lines of each test case contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i \lt v_i \le n$$$; $$$1 \le w_i \le 10^9$$$) — the internet cable connecting house $$$u_i$$$ and house $$$v_i$$$ with latency of $$$w_i$$$. It is guaranteed that the given edges form a connected simple graph.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ do not exceed $$$5000$$$.

Output

For each test case, output $$$n$$$ integers: the minimum total latency that can be achieved for all the houses requiring internet for each $$$k = 1,2,\ldots,n$$$.

Note

In the first test case for $$$k=3$$$, a possible optimal solution is to install servers at vertices $$$2$$$, $$$6$$$ and $$$8$$$ and obtain the following latency:

$$$\text{latency}(2) = 0$$$
$$$\text{latency}(5) = \max(3, 5) = 5$$$
$$$\text{latency}(6) = 0$$$
$$$\text{latency}(8) = 0$$$
$$$\text{latency}(9) = \max(2, 4) = 4$$$

So the total latency is $$$9$$$.

Digital Village (Hard Version)

Examples