문제
상수는 그래프 하나를 가지고 있습니다.
이 그래프는 무방향 가중치 그래프입니다.
또한 이 그래프는 N개의 정점과 M개의 간선을 가지고 있습니다.
상수는 이 그래프의 최소 신장 트리의 값을 알고 싶어 합니다. (최소 신장 트리의 값이란 최소 신장 트리를 이루는 모든 간선 가중치들을 합친 것을 의미합니다.)
하지만 이 그래프는 상수의 성격만큼이나 변덕스러워서 상수가 그래프의 최소 신장 트리를 구하기도 전에 자신의 간선 가중치 하나를 바꾸어 버립니다!
상수는 최소 신장 트리를 구하기 위해 그래프를 설득해 보았지만
그래프는 어떤 간선의 가중치를 몇으로 바꿀 것인지에 대한 정보를 상수에게는 안 주고(...) 프로그래밍을 잘 하는 여러분에게 주었다고 하네요.
여러분은 그래프가 어떤 간선의 가중치를 몇으로 바꿀지에 대한 정보를 Q개 입수했습니다.
여러분은 이 Q개의 쌍에 대해 각각 최소 신장 트리의 가중치를 구해 상수를 도와 주세요!
가중치는 여러분이 최소 신장 트리를 구하면 원래대로 돌아옵니다.
즉 여러분이 다룰 그래프는 원래 그래프와 가중치 하나가 다를 뿐입니다.
입력
첫째 줄에 N M이 주어집니다. N은 정점의 수 M은 간선의 수를 의미합니다. 정점들은 1부터 N까지 번호가 매겨져 있습니다.
다음 M개 줄에는 각각 세 수 a b l (a b ≤ N이고 l ≤ 1 000)가 주어집니다. 이는 a와 b를 연결하는 간선 가중치가 l임을 의미합니다.
다음 줄에는 여러분이 구해야 할 개수 Q가 주어집니다. 다음 Q개 줄에는 두 수 c t가 주어집니다.
이는 c번째(로 입력받은) 간선의 가중치를 t로 바꾼다는 것을 의미합니다(c ≤ M이고 t ≤ 1 000).
그래프의 말에 의하면 자가루프(간선의 시작점과 끝점이 같은 간선)와 중복간선(두 점을 잇는 간선 2개)은 모두 없다고 하네요.
[제약조건]
dataset 1 : N≤1 000. M≤2 000. Q=1.
dataset 2 : N≤50 000. M≤100 000. Q=1.
dataset 3 : N≤50 000. M≤100 000. Q≤100 000. 간선이 바뀔 때 가중치는 늘 줄어듭니다.
dataset 4 : N≤50 000. M≤100 000. Q≤100 000. 추가 제약 없음.
출력
예제
5 61 2 41 3 31 4 32 3 63 4 34 5 146 64 22 71 5
16 9 14 12
로그인해야 코드를 작성할 수 있어요.