최소 스패닝 트리와 쿼리

$Path_i$는 정점이 $i$개인 방향 그래프이다. 모든 $1 \le j < i$에 대해 $j \rightarrow j + 1$ 방향의 간선이 있다.

가중치가 있는 방향 그래프 $G_1$과 방향 그래프 $G_2$의 텐서 곱 $G_1 \times G_2$는 다음과 같이 정의한다.

• 정점 집합은 $\{(u, v) \mid 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 100000$, $1 \le M \le 200000$)

이후 $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}$의 답을 출력한다.