P4172 [WC2006] Waterworks Director

MY City in SC Province has a huge underground water pipe network. Dudu is the waterworks director of MY City (that is, the person in charge of the pipes).

Each day, the water supply company may need to deliver a certain amount of water from $u$ to $v$. Dudu must find a path of pipes from $u$ to $v$ for the company. Then, through an information control center, he instructs the pipes on the path to enter a ready-to-deliver state. Once every pipe on the path is ready, the company can start delivering water. Dudu can handle only one delivery task at a time; he can process the next task only after the current delivery is completed. Before each delivery task, every pipe on the chosen path must undergo a series of preparation operations, such as cleaning and disinfection. At Dudu’s command, these preparations start simultaneously on all pipes of the path. However, due to differences in length and inner diameter, the required preparation time may vary from pipe to pipe. The water supply company always hopes Dudu can find a delivery path such that the time until all pipes on the path are ready is as short as possible. Dudu wants you to help him build a system that selects such a path to meet the company’s requirement. In addition, since the water pipes in MY City are old, some pipes may occasionally fail and become unusable; your program must take this into account. We model the water pipe network of MY City as a simple undirected graph (i.e., without self-loops or multiple edges): pipes are edges, and junctions are nodes. The entire graph has $n$ nodes and $m$ edges, with nodes numbered from $1$ to $n$.

The first line contains three integers, representing the number of junctions (nodes) $n$, the current number of pipes (undirected edges) $m$, and the number of tasks your program needs to process (including both finding a path that meets the requirement and accepting that some pipe has broken) $q$. Each of the next $m$ lines contains three integers $u, v, t$, indicating there is a pipe connecting $(u, v)$ with preparation time $t$. Each of the next $q$ lines contains three integers $k, u, v$, describing a task. Here $k$ indicates the task type: - If $k = 1$, you need to find a path of pipes from $u$ to $v$ that meets the requirement, i.e., the preparation time is minimized. - If $k = 2$, it means the pipe directly connecting $u$ and $v$ is declared scrapped.

For each task with $k = 1$, output a single integer on one line indicating the answer.

#### Constraints For all test points, it is guaranteed that: - $1 \leq n \leq 10^3$, $1 \leq m, q \leq 10^5$. - $1 \leq k \leq 2$, $1 \leq u, v \leq n$, $1 \leq t \leq 10^9$. - The given graph has no multiple edges and no self-loops. Before a pipe is declared scrapped, it is guaranteed that the pipe exists in the graph and has not been scrapped. - The number of scrapped pipes does not exceed $5 \times 10^3$, and at any time the graph is guaranteed to remain connected. Translated by ChatGPT 5