Problem B
Water

A water company is trying to provide water from its pumping station to a mansion. The company owns $n$ water stations, numbered $1 \ldots n$, which are connected by a variety of pipes. Water can flow through both directions of a pipe, but the total amount of water that can flow through the pipe is bounded by the capacity of the pipe.

The water company is constantly improving the pipes, increasing the capacity of various pipes. The water company is conducting $k$ improvements (each of which is permanent after it is executed). An improvement consists of taking a pipe between two locations and increasing its capacity by a fixed amount, or installing a pipe between two locations which are not directly connected by a pipe.

After each improvement, the water company wants to know the maximum amount of water the mansion could receive.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains three integers, $n$ ($2 \le n \le 100$), $p$ ($0 \le p \le \frac{n (n-1)}{2}$), and $k$ ($1 \le k \le 10\, 000$), where $n$ is the number of stations, $p$ is the number of initial pipes, and $k$ is the number of improvements. The first station in the list is always the pumping station, and the second is always the mansion.

The next $p$ lines will describe the pipes in the initial setup. The lines will each contain three integers, $a$, $b$ ($1 \le a < b \le n$) and $c$ ($1 \le c \le 1\, 000$), which indicates that stations $a$ and $b$ are connected by a pipe with capacity $c$. No $(a, b)$ pair will appear more than once in this section.

The next $k$ lines will describe the improvements. The lines will each contain three integers, $a$, $b$ ($1 \le a < b \le n$) and $c$ ($1 \le c \le 1\, 000$), which indicates that the pipe connecting stations $a$ and $b$ has its capacity increased by $c$ (if there is currently no pipe between $a$ and $b$, then one is created with capacity $c$). Note that it is possible for an $(a,b)$ pair to be repeated in this section.

Output

Output $k+1$ integers, each on its own line, describing the maximum amount of water that can reach the mansion. The first number is the amount of water reaching the mansion in the initial configuration. The next $k$ numbers are the amounts of water reaching the mansion after each improvement.

3 2 1
1 3 10
2 3 1
2 3 15

1
10

6 10 2
1 3 2
1 4 6
1 5 1
3 5 8
4 5 7
2 4 3
2 5 4
2 6 1
5 6 9
3 6 5
2 6 9
1 6 3

8
9
12