CF2021E2 Digital Village (Hard Version)

**这是问题的困难版本。在三个版本中，$n$ 和 $m$ 的约束条件不同。只有所有版本的问题都解决了，你才能进行 hack。** Pak Chanek 正在为 Khuntien 村设置互联网连接。这个村庄可以表示为一个连通的简单图，其中有 $n$ 栋房屋和 $m$ 条互联网电缆，每条电缆连接房屋 $u_i$ 和房屋 $v_i$，并且具有延迟 $w_i$。 有 $p$ 栋房屋需要互联网。Pak Chanek 最多可以在 $k$ 栋房屋中安装服务器。需要互联网的房屋将连接到其中一个服务器。但是，由于每条电缆都有其延迟，对于需要互联网的房屋 $s_i$，其经历的延迟将是该房屋与其连接的服务器之间电缆的**最大**延迟。 对于每个 $k = 1,2,\ldots,n$，帮助 Pak Chanek 确定所有需要互联网的房屋所能达到的最小**总**延迟。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 2000$ )。对每个测试用例说明如下： 每个测试用例的第一行包含三个整数 $n$ , $m$ , $p$ ( $2 \le n \le 5000$ ; $n-1 \le m \le 5000$ ; $1 \le p \le n$ )，表示房屋数量、电缆数量和需要网络的房屋数量。 每个测试用例的第二行包含 $p$ 个整数 $s_1, s_2, \ldots, s_p$ ( $1 \le s_i \le n$ )，表示需要上网的房屋。保证 $s$ 中的所有元素都是不同的。 每个测试用例下 $m$ 行每行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i , v_i \le n$ ; $1 \le w_i \le 10^9$）表示一条连接房屋 $u_i$ 和房屋 $v_i$ 的网线，延迟为 $w_i$。保证给定的边构成一个连通的简单图。 保证 $n$ 和 $m$ 之和不超过 $5000$。

对于每个测试用例，输出 $n$ 个整数：对**每个**$k = 1,2,\ldots,n$，计算所有需要上网的房屋所能达到的最小总延迟。 **样例解释** 第一个测试用例中，$k=3$ 的一个的最佳解决方案是在顶点 $2$ 、 $6$ 和 $8$ 安装服务器，并获得以下延迟： - $\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$ 因此总延迟为 $0+5+0+0+4=9$ 。

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