E2. Digital Village (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 < 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$$$.

Example
Input
2
9 8 5
2 5 6 8 9
1 2 1
1 3 2
3 4 10
4 5 3
4 6 5
1 7 10
7 8 4
7 9 2
3 3 2
3 1
1 2 1
2 3 3
1 3 2
Output
34 19 9 4 0 0 0 0 0
2 0 0
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$$$.