[Wc2006]水管局长数据加强版

SC 省 MY 市拥有庞大的地下水管网络。每天，供水公司可能需要将一定量的水从某处输送到另一处。作为 MY 市的水管局长，嘟嘟需要为供水公司选择一条送水路径，并通过控制中心通知路径上的所有水管进入准备送水状态。只有当路径上的每一条水管都准备完毕后，供水公司才能开始送水。嘟嘟一次只能处理一项送水任务，完成当前任务后才能处理下一项。

在每项送水任务开始前，路径上的水管都需要进行清洗、消毒等准备操作。控制中心发出指令后，所有水管会同时开始准备。由于各条水管的长度、内径不同，其准备时间也可能不同，因此整条路径完成准备所需的时间等于路径上准备时间最长的水管所需的时间。

供水公司希望嘟嘟选择一条从起点到终点的路径，使整条路径完成准备所需的时间尽可能短。此外，由于一些水管年代久远，它们可能会发生故障并永久停止使用，你需要在处理任务时考虑这些变化。

可以将 MY 市的水管网络视为一张简单无向图，即图中不存在自环和重边。水管对应图中的边，水管连接处对应图中的结点。

输入格式

第一行包含 $3$ 个整数 $N$ 、 $M$ 、 $Q$ ，分别表示结点数、当前水管数和需要处理的任务数。任务包括查询满足要求的路径，以及宣布某条水管报废。

接下来 $M$ 行，每行包含 $3$ 个整数 $x$ 、 $y$ 、 $t$ ，表示存在一条连接结点 $x$ 与结点 $y$ 的水管，其完成送水准备所需的时间为 $t$ 。结点编号为 $1$ 至 $N$ ，因此 $x,y\in[1,N]$ 。

接下来 $Q$ 行，每行描述一项任务。每项任务的第一个整数为 $k$ ：

若 $k=1$ ，则后跟两个整数 $A$ 、 $B$ ，表示需要查询一条从结点 $A$ 到结点 $B$ 的路径，使路径上所有水管完成准备所需的时间最短；
若 $k=2$ ，则后跟两个整数 $x$ 、 $y$ ，表示直接连接结点 $x$ 与结点 $y$ 的水管报废。保证该操作合法，即在此之前，这条水管存在且尚未报废。

输出格式

对于每项满足 $k=1$ 的任务，按照任务出现的顺序输出一行一个整数，表示从 $A$ 到 $B$ 的所有可用路径中，路径上的全部水管完成准备所需时间的最小值。

样例输入

样例输出

2
3

数据范围

原题数据范围：

$N\le 1000$ ；
$M\le 10^5$ ；
$Q\le 10^5$ ；
测试数据中宣布报废的水管不超过 $5000$ 条；
在任意时刻，当前可用的水管网络均保持连通，即任意两个结点之间都至少存在一条可用的水管路径。

加强版数据范围：

$N\le 10^5$ ；
$M\le 10^6$ ；
$Q\le 10^5$ ；
在任意时刻，当前可用的水管网络均保持连通，即任意两个结点之间都至少存在一条可用的水管路径。

来源与许可

本题为 WC 2006 试题「水管局长数据加强版」，题面与测试数据整理自 BZOJ。

样例 1

输入

输出

2
3