T412729 Tea

有 $n$ 座城市进行茶叶贸易，编号为 $1$ 到 $n$，茶叶的贸易经过 $m$ 条贸易路线。第 $i$ 条贸易路线连接 $u_i, v_i$ 两座城市，耗时为 $w_i$。 现在有 $q$ 名商人，他们有的会开辟新的贸易路线，有的会从已有的贸易路线运送茶叶。 对于每一个运送茶叶的商人，输出他耗费时间的最小可能值。

第一行三个正整数 $n,m,q$，分别代表城市数量，贸易路线数量和商人数量。 接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，分别代表在岛屿 $u_i$ 和岛屿 $v_i$ 之间有一条贸易路线。 接下来 $q$ 行，每行格式如下： - `1 u v w`，开辟一条从城市 $u$ 到城市 $v$ 的耗时为 $w$ 的贸易路线。 - `2 u v`，表示将一批茶叶从城市 $u$ 运送到城市 $v$。

对于每个运送茶叶的商人，输出一个整数，表示耗费时间的最小可能值，如果茶叶无法送达，输出 `-1`。

#### 样例解释 对于第一天，耗时最短的路线为：$3 \rightarrow 2 \rightarrow 4$。 对于第二天，耗时最短的路线为：$2 \rightarrow 4 \rightarrow 1 \rightarrow 5$。 ### 数据规模与约定 对于 $30\%$ 的数据，保证 $1\le q \le 200$。 对于 $100\%$ 的数据，保证 $2 \le n \le 200$，$1 \le m \le \frac{n(n-1)}{2}$，$1 \le q \le 10^5$，$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$。商人开辟的贸易路线不超过 $500$ 条。 数据保证，两座城市之间至多存在 $1$ 条贸易路线，一座城市不存在连接自已的贸易路线。