최소 스패닝 트리와 쿼리

$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}$ 에서의 문제의 정답을 출력해야 한다.