You're given an undirected, connected graph with **N** nodes (numbered from 1
to **N**) and **N** edges. The **i**th edge connects distinct nodes **Ai** and
**Bi**, and has a capacity of **Ci**. No two edges directly connect the same
pair of nodes.

**M** operations will be performed on this graph, one after another. The nature of the **i**th operation is described by the value of **Oi**:

\- If **Oi** = 1, then the **i**th operation is an update, in which the
capacity of the **Xi**th edge is changed to be **Yi**.

\- Otherwise, if **Oi** = 2, then the **i**th operation is a query, in which
you must determine the maximinimax flow in the graph after **Zi** edge
augmentations.

What do any of those terms mean? Let's define them:

\- An edge augmentation is a temporary increase of a certain edge's capacity
by 1 for the current query.

\- The max flow from node **u** to a different node **v** is the usual
definition of maximum flow in computer science (hopefully you're familiar with
it!), with node **u** being the source and node **v** being the sink. Each
edge may transport flow in either direction, so it may be thought of as two
directed edges (one in each direction), both with the same capacity.

\- The minimax flow in the graph is the smallest max flow value across all
pairs of distinct nodes. In other words, min{1 ≤ **u**, **v** ≤ **N**, **u** ≠
**v**} (F(**u**, **v**)), where F(**u**, **v**) is the max flow from node
**u** to node **v**.

\- The maximinimax flow in the graph after **x** edge augmentations is the
largest possible minimax flow which the graph can have after **x** optimal
edge augmentations are applied. Note that each edge can be augmented any non-
negative number of times (as long as the total number of augmentations in the
graph is **x**), and that the chosen edge augmentations are temporary — they
do not change the graph for future operations.

To reduce the size of the output, you should simply output one integer, the
sum of the answers to all of the queries.

### Input

Input begins with an integer **T**, the number of graphs. For each graph,
there is a first a line containing the space-separated integers **N** and
**M**. Then, **N** lines follow, the **i**th of which contains the space-
separated integers **Ai**, **Bi**, and **Ci**. Then, **M** lines follow, the
**i**th of which contains the space-separated integers **Oi**, **Xi**, and
**Yi** (if **Oi** = 1) or **Oi** and **Zi** (if **Oi** = 2).

### Output

For the **i**th graph, print a line containing "Case #**i**: " followed by the
sum of the answers to all queries on that graph.

### Constraints

1 ≤ **T** ≤ 85
3 ≤ **N** ≤ 500,000
1 ≤ **M** ≤ 500,000
1 ≤ **Ai**, **Bi**, **Xi** ≤ **N**
1 ≤ **Ci**, **Yi** ≤ 1,000,000
0 ≤ **Zi** ≤ 1,000,000,000,000
1 ≤ **Oi** ≤ 2

### Explanation of Sample

In the first graph, the max flow between any two nodes is 10, so the minimax
flow is also 10. If we do no edge augmentations, then the maximinimax flow is
still 10. In the second graph, the maximinimax flow is initially 3, but is
then increased to 5 before the second query for a total of 8. In the third
graph, the maximinimax flow is initially 7 (between node 2 and any other
node). If we augment the edge from node 3 to node 2 twice, then the max flow
between node 2 and any other node is now 9. The max flow between any other
pair of nodes was already greater than 9, so the minimax flow is now 9. We
can't do any better than that, so the maximinimax flow is also 9.