최소 신장 선인장

[그림] 선인장 그래프의 예시

선인장 그래프(cactus graph)는 모든 간선이 최대 한 개의 사이클에 속하는 연결된 무방향 그래프다. 즉, 서로 다른 두 사이클이 최대 한 개의 공통 정점을 가지는 무방향 연결 그래프다.

신장 부분 그래프(spanning subgraph)는 기존 그래프의 모든 정점을 포함하는 부분 그래프(subgraph)다. 신장 부분 그래프가 선인장 그래프이면 이를 신장 선인장(spanning cactus)이라고 한다. 그래프의 간선에 비용이 주어질 때, 간선 비용의 합이 최소인 신장 선인장을 최소 신장 선인장(minimum spanning cactus)이라고 한다.

정점 $N$개, 비용이 있는 무방향 간선 $M$개로 이루어진 선인장 그래프가 주어진다. 모든 정점에는 $1$부터 $N$까지 번호가 붙어 있다. 먼저 주어진 선인장 그래프의 최소 신장 선인장의 비용을 출력하고, 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• $u$ $v$ $d$ : 정점 $u$와 정점 $v$를 잇는 간선의 비용을 $d$로 바꾸고, 최소 신장 선인장의 비용을 출력한다.

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 쿼리의 개수 $Q$가 주어진다. ($2 \le N \le 100\,000$, $N-1 \le M \le 150\,000$, $1 \le Q \le 100\,000$)

두 번째 줄부터 $M$개의 줄에 걸쳐서 간선을 나타내는 $(x,y,c)$가 순서대로 주어진다. $x$와 $y$는 간선의 양 끝 정점이고, $c$는 간선의 가중치다. 두 정점 사이에 두 개 이상의 간선이 있는 경우는 주어지지 않는다. ($1 \le x, y \le N$, $-10^9 \le c \le 10^9$)

다음 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

첫 번째 줄에는 처음에 주어진 선인장 그래프의 최소 신장 선인장의 비용을 출력한다.

두 번째 줄부터 $Q$개의 줄에 걸쳐서 쿼리의 결과를 출력한다.