Minimum spanning tree and queries

$Path_i$ is a directed graph with $i$ vertices, and for every $1 \le j < i$ there is an edge $j \rightarrow j + 1$.

The tensor product $G_1 \times G_2$ of a weighted directed graph $G_1$ and a directed graph $G_2$ is defined as follows.

• The vertex set is $\{(u, v) \mid u \in G_1, v \in G_2\}$. It has $|G_1| \times |G_2|$ vertices.
• Two vertices $(u_1, v_1)$ and $(u_2, v_2)$ are joined by an undirected edge if $G_1$ has an edge $u_1 \rightarrow u_2$ and $G_2$ has an edge $v_1 \rightarrow v_2$.
• The weight of that edge equals the weight of the edge $u_1 \rightarrow u_2$ in $G_1$.

You are given a directed graph $G$ with $N$ vertices and $M$ edges, and each edge has a positive integer weight. Consider $G \times Path_i$. It is undirected, and each of its edges has a positive integer weight. For every $2 \le i \le Q + 1$, output the total weight of a minimum spanning tree of $G \times Path_i$. The input guarantees that every $G \times Path_i$ asked in a query has a spanning tree.

The first line contains three integers $N$, $Q$, and $M$ ($1 \le N, Q \le 100000$, $1 \le M \le 200000$).

Each of the next $M$ lines contains three integers $u_i$, $v_i$, and $w_i$, meaning there is an edge $u_i \rightarrow v_i$ with weight $w_i$ ($1 \le u_i, v_i \le N$, $1 \le w_i \le 30$).

Print $Q$ lines. The $i$-th line contains the answer for $G \times Path_{i+1}$.