신촌 도로망 관리와 쿼리

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$번의 도로 관리비 변동에 대하여, 각각 관리비 변경 후 관리비 합의 최솟값을 새로운 줄에 출력한다.