Tower Network Bandwidth Optimization

You are given a network of n towers connected by m links. Each link has an associated bandwidth. The network is initialized such that the bandwidth between a tower and itself is \(\infty\) and between distinct towers with no direct connection is 0. Using the direct links, the maximum effective bandwidth (defined as the maximum of the minimum bandwidths along any path) between each pair of towers is computed via the Floyd–Warshall algorithm. In other words, for any two towers i and j, the effective bandwidth is updated according to the formula:

$$\text{bw}[i][j] = \max\Big(\text{bw}[i][j], \min(\text{bw}[i][k],\,\text{bw}[k][j])\Big)$$

The problem includes two types of queries:

• Type 1: Report the maximum effective bandwidth among all pairs of distinct towers.
• Type 2: Update the connection between two towers to a new bandwidth if it is higher than the current connection, and then recalculate the effective bandwidths for the network.

You must process the queries in the given order. All input is read from standard input and all output should be printed to standard output.

inputFormat

The first line contains three integers n, m and q -- the number of towers, the number of initial connections, and the number of queries respectively.

The next m lines each contain three integers a, b and c representing a connection between towers a and b with bandwidth c.

The following q lines describe the queries. Each query is in one of the following formats:

• 1 — A type 1 query which asks for the current maximum effective bandwidth among all pairs of towers.
• 2 x y b — A type 2 query where the connection between towers x and y is updated to bandwidth b if b is greater than the current direct connection bandwidth. After an update, the network connectivity should be recalculated.

outputFormat

For each query of type 1, output a single line containing the maximum effective bandwidth among all pairs of distinct towers.

## sample

4 3 3
1 2 5
2 3 10
3 4 20
1
2 1 4 25
1

20
25

</p>