18933번 - 최소 스패닝 트리와 쿼리 분류

$Path_i$는 $i$ 개의 정점을 가진 방향 그래프로, 모든 $1 \le j < i$ 에 대해 $j \rightarrow j + 1$ 로 가는 간선이 존재한다.

가중치 있는 방향 그래프 $G_1$ 과 방향 그래프 $G_2$ 의 텐서 곱 (tensor product) $G_1 \times G_2$ 는 다음과 같이 정의된다:

• 정점 집합은 $\{(u, v)|u \in G_1, v \in G_2\}$ 의 형태다. 정점 집합의 크기는 $|G_1| \times |G_2|$ 이다.
• 두 정점 $(u_1, v_1), (u_2, v_2)$ 를 잇는 무방향 간선이 존재한다는 것은, $G_1$ 에 $u_1 \rightarrow u_2$ 방향의 간선, $G_2$ 에 $v_1 \rightarrow v_2$ 방향의 간선이 있음을 뜻한다. 
• 간선의 가중치는, $G_1$에서 두 정점 $u_1 \rightarrow u_2$를 잇는 간선의 가중치와 동일하다. 

$N$ 개의 정점과 $M$ 개의 간선을 가진 방향 그래프 $G$ 가 입력으로 주어진다. 각 간선에는 양의 정수 가중치가 부여되어 있다. $G \times Path_i$ 라는 그래프를 생각하자. 이 그래프는 무방향이고 각 간선에 양의 정수 가중치가 부여되어 있다. 모든 $2 \le i \le Q + 1$에 대해, $G \times Path_i$ 의 최소 스패닝 트리의 간선 가중치 합을 출력하라. 쿼리로 들어오는 모든 $G \times Path_i$ 에 대해 스패닝 트리가 항상 존재하게끔 입력이 주어짐이 보장된다.

첫 번째 줄에 세 정수 $N, Q, M$ 이 주어진다. ($1 \le N, Q \le 100\,000, 1 \le M \le 200\,000$)

이후 $M$ 개의 줄에 세 개의 정수 $u_i, v_i, w_i$ 가 주어진다. $u_i \rightarrow v_i$ 방향의 가중치 $w_i$ 의 간선이 존재한다는 뜻이다. ($1 \le u_i, v_i \le N, 1 \le w_i \le 30$) 

$Q$ 개의 줄을 출력하라. 이 중 $i$ 번째 줄에는 $G \times Path_{i + 1}$ 에서의 문제의 정답을 출력해야 한다.