E2. 数字村庄（困难版本）

时间限制：每个测试 $2$ 秒
内存限制：$256$ MB

这是本题的困难版本。在三个版本中，$n$ 和 $m$ 的约束不同。只有解决了所有版本的题目，你才能进行 Hack。

题目描述

Pak Chanek 正在为 Khuntien 村庄建立互联网连接。该村庄可以表示为一个连通简单图，包含 $n$ 座房屋和 $m$ 条互联网电缆，第 $i$ 条电缆连接房屋 $u_i$ 和 $v_i$，延迟为 $w_i$。

有 $p$ 座房屋需要互联网。Pak Chanek 可以在最多 $k$ 座房屋中安装服务器。需要互联网的房屋将被连接到其中一个服务器。然而，由于每条电缆都有其延迟，需要互联网的房屋 $s_i$ 所经历的延迟等于该房屋与其所连接的服务器之间的电缆的最大延迟。

对于每个 $k = 1, 2, \dots, 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, \dots, s_p$（$1 \le s_i \le n$），表示需要互联网的房屋。保证 $s$ 中的所有元素互不相同。

接下来的 $m$ 行中的第 $i$ 行包含三个整数 $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$ 的互联网电缆及其延迟。保证给定的边构成一个连通简单图。

保证所有测试用例的 $n$ 之和以及 $m$ 之和均不超过 $5000$。

输出格式

对于每个测试用例，输出 $n$ 个整数：对于每个 $k = 1, 2, \dots, n$，所有需要互联网的房屋所能达到的最小总延迟。

示例

输入

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

输出

34 19 9 4 0 0 0 0 0
2 0 0

样例解释

在第一个测试用例中，对于 $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$

因此总延迟为 $9$。