문제

물 회사가 그들의 펌프 시설로부터 맨션으로 물을 공급하려고 한다.

회사는 1부터 N까지 번호가 붙여진 N개의 시설을 가지고 있으며, 각 시설은 서로 파이프로 연결되어 있다. (이때 펌프 시설은 1번, 맨션은 2번이다.)

물은 파이프의 양방향으로 흐를 수 있지만, 파이프의 용량 이상으로 흐르지는 못한다.

회사는 현재 파이프의 용량을 늘리는 K개의 개선 사업에 착수했다. 

개선 사업은 어떤 두 지점을 연결하는 파이프의 용량을 증가시키거나, 기존에는 직접 연결되어 있지 않은 두 지점을 직접 연결하는 파이프를 건설하는 것이다.

(이때, 각각의 개선 사업에 의한 파이프의 용량 증가는 영구적이다.)

회사는 각각의 개선 사업이 끝난 후에, 맨션에 공급할 수 있는 물의 최대값을 알고 싶어한다.

입력

각 입력은 하나의 테스트 케이스로만 구성되어 있다.

첫 번째 줄에 시설의 개수 N(2 ≤ N ≤ 100), 기존에 설치된 파이프의 개수 P(0 ≤ P ≤ N(N - 1) / 2), 개선 사업의 개수 K(1 ≤ K ≤ 10,000)가 하나의 공백을 사이에 두고 주어진다. 

그 다음부터 P개의 줄에 걸쳐 기존에 설치되어있는 파이프의 정보가 주어진다. 각 줄마다 서로 연결된 지점 A, B(1 ≤ A < B ≤ N)와 A, B를 잇는 파이프의 용량 C(1 ≤ C ≤ 1,000)가 하나의 공백을 사이에 두고 주어진다. 각각의 파이프 정보에 대해 A, B쌍은 중복되어 주어지지 않는다.

그 다음부터 K개의 줄에 걸쳐 개선 사업의 정보가 주어진다. 각 줄마다 서로 연결된 지점 A, B(1 ≤ A < B ≤ N)와 A, B를 잇는 파이프 용량의 증가량 C(1 ≤ C ≤ 1,000)가 하나의 공백을 사이에 두고 주어진다. 즉, A와 B를 잇는 파이프의 용량을 C만큼 증가시킨다는 뜻이다. (A와 B 사이에 설치되어있던 파이프가 없다면, C의 용량을 가진 파이프를 새로 건설한다.) 각각의 개선 사업에 대해 중복되는 A, B쌍이 주어질 수 있다.

출력

첫 번째 줄에는 기존에 설치되어있던 파이프를 통해 공급할 수 있는 물의 최대값을, 다음부터 K개의 줄에 걸쳐 각각의 개선이 끝난 이후에 공급할 수 있는 물의 최대값을 출력한다.