Water Supply Upgrades

A water company sends water from its pumping station to a mansion. The company runs $n$ water stations, numbered 1 to $n$, joined by pipes. Water flows through a pipe in either direction, and the total amount of water that passes through a pipe never exceeds the capacity of that pipe.

The company keeps improving its pipes. It carries out $k$ improvements, and an improvement is permanent once it is done. One improvement raises the capacity of the pipe between two stations by a fixed amount. If those two stations have no pipe between them yet, the improvement installs one with that capacity.

After each improvement the company wants to know the largest amount of water the mansion can receive.

The input contains a single test case. The first line has three integers $n$ ($2 \le n \le 100$), $p$ ($0 \le p \le n(n-1)/2$) and $k$ ($1 \le k \le 10000$), where $n$ is the number of stations, $p$ is the number of pipes already in place, and $k$ is the number of improvements. Station 1 is the pumping station and station 2 is the mansion.

Each of the next $p$ lines describes one pipe of the initial setup with three integers $a$, $b$ ($1 \le a < b \le n$) and $c$ ($1 \le c \le 1000$), meaning stations $a$ and $b$ are joined by a pipe of capacity $c$. No pair $(a, b)$ appears more than once in this part of the input.

Each of the next $k$ lines describes one improvement with three integers $a$, $b$ ($1 \le a < b \le n$) and $c$ ($1 \le c \le 1000$), meaning the capacity of the pipe between stations $a$ and $b$ grows by $c$. If there is no pipe between $a$ and $b$ at that moment, one of capacity $c$ is installed. A pair $(a, b)$ may repeat in this part of the input.

Print $k+1$ integers, one per line. The first is the largest amount of water that reaches the mansion in the initial setup. The next $k$ numbers are that amount after each improvement, in the order the improvements are given.