최단 경로 게임

Albert는 무방향 그래프에서 경로 찾는 게임을 즐겨한다. 다만 주어진 그래프에서 최단 경로를 찾는것은 재미가 없으므로, 현재 그래프에 새로운 간선을 추가하거나 혹은 이전에 추가했던 간선을 삭제하며 계속 그래프를 바꿔가며 최단 경로를 찾는 게임을 고안했다.

처음에 정점이 $N$ 개이고 간선이 $M$ 개인 그래프 $G$ 을 만드는데, 정점은 $1, 2, \dots, N$ 으로 번호가 붙어있다. $i$ 번째 간선은 $(X\_i, Y\_i, C\_i)$ 로 표현하는데 정점 $X\_i, Y\_i$ 를 잇고 가중치가 $C\_i$ 임을 나타낸다. 예를 들어 아래 그림은 $N = 6$ , $M = 5$ , $X = \[1, 2, 1, 4, 5]$ , $Y = \[2, 3, 4, 3, 6]$ , $C = \[8, 7, 10, 2, 4]$ 인 그래프를 보여준다. 간선에 방향성이 없음에 유의하자. 두 정점을 연결하는 간선이 여럿 있을 수 있지만 (예제 참고) 모든 간선은 $X\_i \ne Y\_i$ 를 만족한다.

이렇게 처음에 사용할 그래프 $G$ 을 만든 후, 총 $Q$ 개의 연산을 수행하는데, 연산에는 3가지 종류가 있다. $k$ 번째 연산의 종류는 $R\_k \in \\{1, 2, 3\\}$ 으로 표현하자.

1번 연산: 현재 그래프의 점수를 구한다. 그래프의 정점 쌍 $(i, j)$ 중 $i \ne j$ 이며 $i$ 와 $j$ 사이에 경로가 존재한다면 그 중 최단 경로의 가중치를 모두 더한 것이 그래프의 점수가 된다. 경로가 존재하지 않으면 해당 정점 쌍은 점수 계산에서 고려하지 않는다. Albert는 이 점수를 종이에 순서대로 적는다.
2번 연산: 두 정점 $A\_k$ 와 $B\_k$ 를 잇는 가중치가 $W\_k$ 인 간선을 추가한다. 이미 그래프에 두 정점을 잇는 간선이 있더라도 새로운 간선을 추가한다.
3번 연산: 2번 연산을 통해 추가된 간선 중 가장 마지막에 추가된 간선을 삭제한다. 단, 현재 그래프에 2번 연산으로 추가된 간선이 없다면 이 연산은 아무런 효과가 없다.

다만 $A\_k, B\_k, W\_k$ 는 $R\_k = 2$ 인 경우에만 정의되므로 편의상 $R\_k \ne 2$ 인 경우엔 $A\_k = B\_k = W\_k = 0$ 이라 하자.

예를 들어 위 예제의 그래프에 $Q = 9$ 개의 연산을 적용한다고 하고, 연산의 종류는 $R = \[1, 2, 1, 2, 1, 3, 1, 3, 1]$ , 그리고 $A = \[0, 3, 0, 2, 0, 0, 0, 0, 0]$ , $B = \[0, 5, 0, 6, 0, 0, 0, 0, 0]$ , $W = \[0, 1, 0, 2, 0, 0, 0, 0, 0]$ 라 하자.

$R\_1 = 1$ : 이 그래프의 점수를 구하려면 다음 정점 쌍의 최단 경로를 구해야 한다: $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (5, 6)$ . 다른 정점 쌍은 최단 경로가 존재 하지 않는 정수 쌍이다 -- 예를 들어 $(1, 5)$ 나 $(4, 5)$ 사이에는 경로가 없다. 이 일곱개의 정점 쌍간 최단거리는 순서대로 $8, 12, 10, 7, 9, 2, 4$ 이므로 이를 모두 더한 값이 그래프의 점수가 되고, 이는 52이다.
$R\_2 = 2$ : 이 그래프에 간선을 추가하는데, $A\_2 = 3$ , $B\_2 = 5$ 이므로 $(3, 5)$ 를 잇는 간선을 추가하고 그 가중치는 $W\_2 = 1$ 이 된다. 아래 좌측 그림의 그래프가 새 간선이 추가된 모습을 나타낸다.
$R\_3 = 1$ : 앞선 경우와 마찬가지로 점수 계산을 해야한다. 이제 1, 2, 3, 4번 정점과 5, 6번 정점 사이에도 경로가 존재하므로 이를 포함하여 계산해야하고, 이 점수는 118이다.
$R\_4 = 2$ : 이 그래프에 $(2, 6)$ 은 연결하는 가중치가 2인 간선을 추가해야 하며 아래 우측 그림의 그래프가 두 번째 간선이 추가된 모습을 보여준다.
$R\_5 = 1$ : 새로 추가된 간선을 이용하면 최단 경로가 이전 그래프에 비해 짧아지는 경우가 생긴다. 예를 들어 $(2, 6)$ 사이의 최단 경로가 이전에는 12이었지만 이제 새로운 간선을 이용하면 최단 경로가 2로 줄어든다. 이 그래프의 점수는 99이다.
$R\_6 = 3$ : 가장 마지막에 추가한 간선인 $(2, 6)$ 을 연결하는 간선을 삭제한다. 이후 그래프는 아래 그림의 좌측과 같다.
$R\_7 = 1$ : 이 그래프의 점수는 앞서 계산한대로 118이다.
$R\_8 = 3$ : 현재 그래프에 (아래 그림의 좌측) 가장 마지막에 추가한 간선인 $(3, 5)$ 를 연결하는 간선을 삭제한다. $(2, 6)$ 은 연결하는 간선은 이미 삭제되었기 때문에 다시 삭제할 수는 없다. 이리하여 얻어진 그래프는 맨 처음에 주어졌던 간선이 5개인 그래프이다.
$R\_9 = 1$ : 이 그래프의 점수는 앞서 계산한대로 52점이다.
연산을 모두 마친 후 Albert의 종이에는 그래프들의 점수인 "52 118 99 118 52"가 순서대로 적혀있다.

입력으로 $N, M, Q$ , $X, Y, C$ 그리고 $R, A, B$ 가 주어졌을 때 1번 연산에서 구한 점수들을 순서대로 구해보자 -- Albert는 당신의 도움을 받아 자신의 답이 맞는지 확인해보고싶다.

최단 경로 게임

문제

입력

출력

제한