The city of MY in SC Province has a vast underground water pipe network. Dudu is the director of the water pipe bureau (the person in charge of the pipes). Dudu's job as the director is as follows: every day, the water supply company may need to transport a certain amount of water from point $x$ to point $y$. Dudu needs to find a path of water pipes from $A$ to $B$ for the supply company, and then notify the pipes along the path via an information control center to enter a state of preparation for water delivery. Once every pipe on the path is ready, the water supply company can begin transporting water. Dudu can only handle one water delivery task at a time, and can only process the next task after the current one is completed.

Before processing each water delivery task, the pipes along the path must undergo a series of preparatory operations, such as cleaning and disinfection. Upon Dudu's command from the control center, the preparatory operations for these pipes begin simultaneously. However, due to the different lengths and internal diameters of each pipe, the time required for these preparations may vary. The water supply company always hopes that Dudu can find a water delivery path such that the time required for all pipes on the path to be ready is as short as possible. Dudu hopes you can help him complete such a path-selection system to meet the requirements of the water supply company. Additionally, because the water pipes in MY city are old, some pipes may occasionally malfunction and become unusable; your program must take this into account.

We can think of the water pipe network in MY city as a simple undirected graph (i.e., no self-loops or multiple edges): water pipes are the edges in the graph, and the connections between pipes are the nodes in the graph.

Input

The first line of the input file contains 3 integers: $N$, $M$, and $Q$, representing the number of pipe connections (nodes), the current number of water pipes (undirected edges), and the number of tasks your program needs to process (including finding a path that meets the requirements and accepting the fact that a certain water pipe has broken down), respectively.

The following $M$ lines each contain 3 integers $x$, $y$, and $t$, describing a corresponding water pipe. $x$ and $y$ represent the labels of the nodes at both ends of the pipe, and $t$ represents the time required to prepare for water delivery. We label the nodes from $1$ to $N$, so all $x$ and $y$ are in the range $[1, N]$.

The following $Q$ lines each describe a task. The first integer is $k$: if $k=1$, it is followed by two integers $A$ and $B$, indicating that you need to find a water pipe path from $A$ to $B$ that meets the requirements for the water supply company; if $k=2$, it is followed by two integers $x$ and $y$, indicating that the water pipe directly connecting $x$ and $y$ is declared broken (guaranteed to be valid, i.e., a water pipe directly connecting $x$ and $y$ that has not yet been declared broken must exist before this).

Output

For each $k=1$ task in the input file in order, you need to output a single number followed by a carriage return/newline character. This number represents the time required for all pipes in the water pipe path you found to complete their preparations (which, of course, should be the shortest possible).

Examples

Input 1

4 4 3
1 2 2
2 3 3
3 4 2
1 4 2
1 1 4
2 1 4
1 1 4

Output 1

2
3

Constraints

$N \le 1000$ $M \le 100000$ $Q \le 100000$

In the test data, the number of water pipes declared broken does not exceed $5000$; and at any time, the water pipe network we consider is connected, meaning there is at least one water pipe path from any node $A$ to any node $B$.