Road Network Management and Queries in Sinchon

In 2025, five universities in Sinchon, Sogang University, Sookmyung Women's University, Yonsei University, Ewha Womans University, and Hongik University, decided to build and manage a road network for smooth travel across Sinchon.

Sinchon has $N$ vertices, and $M$ undirected roads connect pairs of distinct vertices. Two vertices are joined by at most one direct road, and any two vertices are connected by some path.

Each road is managed by one of the five schools. Every road needs an annual maintenance fee that depends on the school managing it. All roads managed by the same school have the same fee.

From 2125 on, the schools' budgets ran short, and the fees started to change from year to year. The five schools agreed to manage roads so that for any two vertices, a path between them exists using only managed roads. The remaining roads stay unmanaged for that year. For each year, you are given the new fee of each school. Compute the minimum total fee needed to keep the roads managed as agreed.

The first line contains $N$, $M$, and $Q$ separated by spaces. $(1 \le N \le 5 \times 10^4;$ $N-1 \le M \le 10^5;$ $1 \le Q \le 2 \times 10^4)$

Each of the next $M$ lines contains $u_i$, $v_i$, and $z_i$ separated by spaces, meaning road $i$ connects vertices $u_i$ and $v_i$ and is managed by school $z_i$. $(1 \le u_i, v_i \le N;$ $u_i \neq v_i;$ $z_i \in \{A, B, C, D, E\})$ A, B, C, D, and E stand for Sogang University, Sookmyung Women's University, Yonsei University, Ewha Womans University, and Hongik University, in that order.

Each of the last $Q$ lines, starting from line $M+2$, contains the new fees $a_j$, $b_j$, $c_j$, $d_j$, and $e_j$ separated by spaces, in the order of the five schools above. $(0 \le a_j, b_j, c_j, d_j, e_j \le 10^7)$

For each of the $Q$ fee changes, print on its own line the minimum total fee after the change.