32131번 - 연결하기 서브태스크

다음과 같은 과정을 통해 만들어진 무방향 가중치 연결그래프 $G=(V, E)$가 주어진다.

1. 정점의 집합 $V$와 간선의 집합 $E$에 대해 $V= \emptyset$, $E= \emptyset$으로 둔다. 입력 제한을 만족하는 양의 정수 $N$과 $M$을 선택한다.
2. 정점 $1$, $2$를 추가하고, 간선 $\{1, 2 \}$를 추가한다. ($V = \{1, 2 \}$, $E = \{ \{1, 2 \} \}$)
3. 현재 $V$에 없는 가장 작은 양의 정수에 해당하는 번호를 가지는 정점 $v$를 추가한다.
4. 간선 $e = \{ u_1, u_2 \} \in E$를 뽑은 후, 간선의 양 끝점을 각각 $v$와 연결한다. ($\{ u_1, v \}$, $\{ u_2, v \}$를 $E$에 추가한다.)
5. 정점의 개수 $|V|$가 $N$ 미만이라면 3번 단계로 돌아가서 이후 과정을 다시 반복한다. $N$ 이상이라면 6번 단계로 넘어간다.
6. 간선의 개수가 $M$보다 많다면 $G = (V, E \setminus \{ e \})$가 연결그래프가 되게 하는 $e \in E$를 골라서 $E$에서 제거한다. 즉, $e$를 제거했을 때도 $G$가 연결그래프인 간선 $e$를 선택하여 제거한다. 간선의 개수가 $M$개가 될 때까지 이 과정을 반복한다.
7. 정점 번호를 셔플하고 각 간선에 가중치를 부여한다. 가중치는 $1$ 이상 $10^9$ 이하의 양의 정수이다.

예를 들어, 다음은 올바른 입력에 해당하는 그래프이다.

그러나, 다음은 올바르지 않은 입력에 해당하는 그래프이다.

$G$의 서로 다른 정점 $K$개가 주어질 때, 간선의 부분집합 $E' \subseteq E$를 적절히 골라 $G'=(V, E')$에서 주어진 $K$개의 정점이 같은 연결성분에 있게 해야 한다. 이러한 $E'$ 중 $E'$에 속하는 간선의 가중치 합의 최솟값을 구하여라. 다시 말해, 주어진 $K$개의 정점을 모두 연결하는 부분그래프의 최소 가중치를 구하여라.

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$개의 줄에 걸쳐 $i$번째 간선을 나타내는 세 정수 $s_i$, $e_i$, $w_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 간선이 $s_i$와 $e_i$를 연결하는 가중치 $w_i$의 간선이라는 뜻이다.

$(M+2)$번째 줄에는 $K$가 주어진다.

$(M+3)$번째 줄에는 $K$개의 서로 다른 정점 $V_1, V_2, \cdots, V_K$가 공백으로 구분되어 주어진다.

첫 번째 줄에 답에 해당하는 정수를 출력한다.

• 주어지는 모든 수는 정수이다.
• $3 \le N \le 10\,000$
• $N-1 \le M \le 20\,000$
• $1 \le s_i, e_i \le N$ ($1 \le i \le M$)
• $1 \le w_i \le 10^9$ ($1 \le i \le M$)
• $2 \le K \le N$
• $1 \le V_i \le N$ ($1 \le i \le K$)
• $V_1, V_2, \cdots, V_K$는 모두 서로 다르다.

예제 4의 답은 다음과 같다.