신촌 도로망 관리와 쿼리

2025년, 신촌의 다섯 대학교인 서강대, 숙명여대, 연세대, 이화여대, 홍익대는 신촌 안을 원활하게 통행할 수 있도록 도로망을 구축하고 관리하기로 했다.

신촌은 $N$개의 정점으로 이루어져 있고, 서로 다른 두 정점을 잇는 방향 없는 도로가 $M$개 건설되어 있다. 두 정점을 직접 잇는 도로는 최대 한 개만 있으며, 어떤 두 정점을 선택하더라도 그 사이를 잇는 경로가 존재한다.

각 도로는 다섯 학교 중 한 곳이 담당하여 관리한다. 도로를 관리하려면 매년 관리비가 든다. 관리비는 관리하는 학교에 따라 정해지므로, 같은 학교가 관리하는 도로의 관리비는 모두 같다.

2125년부터 학교마다 예산이 부족해져 관리비가 해마다 바뀌게 되었다. 그래서 다섯 학교는 어떤 두 정점을 선택하더라도 관리된 도로만 사용해 그 두 정점을 잇는 경로가 존재하도록 도로를 관리하고, 나머지 도로는 한 해 동안 관리하지 않기로 합의했다. 매년 각 학교의 새 관리비가 주어지면, 합의한 대로 도로를 관리하기 위한 관리비 합의 최솟값을 구해야 한다.

첫 번째 줄에 정점의 개수 $N$, 도로의 개수 $M$, 관리비가 바뀌는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 5 \times 10^4;$ $N-1 \le M \le 10^5;$ $1 \le Q \le 2 \times 10^4)$

두 번째 줄부터 $M$개의 줄에 걸쳐 도로 정보가 주어진다. $i$번째 줄에는 도로 $i$가 잇는 두 정점 $u_i$, $v_i$와 그 도로를 관리하는 학교를 나타내는 문자 $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, E는 각각 서강대, 숙명여대, 연세대, 이화여대, 홍익대를 가리킨다.

$M+2$번째 줄부터 $Q$개의 줄에 걸쳐 새로 정해진 학교별 관리비 $a_j$, $b_j$, $c_j$, $d_j$, $e_j$가 공백으로 구분되어 주어진다. 순서는 위의 다섯 학교 순서와 같다. $(0 \le a_j, b_j, c_j, d_j, e_j \le 10^7)$

관리비가 $Q$번 바뀔 때마다, 관리비를 변경한 뒤의 관리비 합의 최솟값을 새로운 줄에 출력해야 한다.