상수도 증설

어떤 상수도 회사가 양수장에서 저택까지 물을 보낸다. 회사가 관리하는 상수도 시설은 $n$개이고 1번부터 $n$번까지 번호가 붙어 있으며, 시설끼리는 관으로 이어져 있다. 물은 관의 양방향으로 흐를 수 있고, 관 하나를 지나는 물의 총량은 그 관의 용량을 넘지 못한다.

회사는 관을 계속 개선한다. 개선 작업은 모두 $k$번 이뤄지고, 한 번 끝낸 작업은 되돌리지 않는다. 개선 작업 하나는 두 시설을 잇는 관의 용량을 정해진 만큼 늘린다. 두 시설 사이에 관이 아직 없으면 그 용량으로 관을 새로 놓는다.

회사는 개선 작업을 한 번 할 때마다 저택이 받을 수 있는 물의 최대량을 알고 싶다.

입력은 테스트 케이스 하나로 이뤄진다. 첫째 줄에 세 정수 $n$ ($2 \le n \le 100$), $p$ ($0 \le p \le n(n-1)/2$), $k$ ($1 \le k \le 10000$)가 주어진다. $n$은 시설의 개수, $p$는 처음에 놓여 있는 관의 개수, $k$는 개선 작업의 횟수다. 1번 시설이 양수장이고 2번 시설이 저택이다.

다음 $p$개의 줄에는 처음에 놓여 있는 관이 주어진다. 각 줄에는 세 정수 $a$, $b$ ($1 \le a < b \le n$), $c$ ($1 \le c \le 1000$)가 주어지며, $a$번 시설과 $b$번 시설이 용량 $c$인 관으로 이어져 있다는 뜻이다. 이 부분에서 같은 $(a, b)$ 쌍은 두 번 이상 나오지 않는다.

다음 $k$개의 줄에는 개선 작업이 주어진다. 각 줄에는 세 정수 $a$, $b$ ($1 \le a < b \le n$), $c$ ($1 \le c \le 1000$)가 주어지며, $a$번 시설과 $b$번 시설을 잇는 관의 용량이 $c$만큼 늘어난다는 뜻이다. 그 시점에 두 시설 사이에 관이 없으면 용량이 $c$인 관을 새로 놓는다. 이 부분에서는 같은 $(a, b)$ 쌍이 여러 번 나올 수 있다.

$k+1$개의 정수를 한 줄에 하나씩 출력한다. 첫 번째 수는 처음 상태에서 저택에 도달하는 물의 최대량이다. 이어지는 $k$개의 수는 개선 작업을 하나씩 끝낸 뒤의 최대량이며, 개선 작업이 주어진 순서대로 출력한다.