E3. Digital Village (Extreme Version)
data structures; dfs and similar; dp; dsu; graphs; greedy; math; trees
This is the extreme 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.
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 10^4\)). The description of the test cases follows.The first line of each test case contains 3 integers \(n\), \(m\), \(p\) (\(2 \le n \le 2 \cdot 10^5\); \(n-1 \le m \le 2 \cdot 10^5\); \(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 \(2 \cdot 10^5\).
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\).
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\).