연결하기

다음과 같은 과정을 통해 만들어진 무방향 가중치 연결그래프 $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의 답은 다음과 같다.