#12007. 虚实

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

「能使敌自至者,利之也;能使敌不得至者,害之也。故敌佚能劳之,饱能饥之,安能动之。出其所不趋,趋其所不意。」
——《孙子兵法·虚实》

某年月日,白国和委国之间的战争爆发了!然而,在委国指挥官委兆的眼里,白国人不堪一击。

现在他手上有一张白国的地图,发现白国有n个据点,m条无向道路,他们有各自的长度。于是他决定按一定顺序破坏白国的一些据点,使得所有连接这些据点与其他据点的道路无法通行。同时,为了更有效率的攻城略地,也为了满足委兆的成就感,他有时还想知道当前某两个据点间的最短路径长。请编程满足他的要求。

输入格式

第一行两个正整数 。

接下来 行,每行有三个数 表示一条连接 的无向边。

接下来一行一个正整数 。

接下来 行,每行是两个数 1 a 或是三个数 2 a b,含义如题面所述。

输出格式

对于每个 2 a b 操作,输出对应的结果。

若两点不连通,输出 -1。

样例

样例输入

4 4
1 2 6
3 4 1
1 3 4
1 4 9
3
2 1 4
1 3
2 1 4

样例输出

5
9

数据范围与提示

对于 的数据 。

另有 的数据 没有第一种操作。

另有 的数据 。

对于 的数据 保证所有的操作合法。

本题考察 Floyd 算法。