配点: 100 点
問題
JOI国有,n 岛屿,每个岛屿都有 1 从 n 编号。现在,JOI国正在整备连接各岛屿之间的航线网络。
你在处理船票的售票中心工作。JOI国有很多人希望使用船只以尽可能便宜的方式在岛屿之间旅行,他们会在订单表上写上出发地和目的地,然后送到你这里。
你的工作是在收到客户的订单表后,立即通过换乘几艘船,计算出连接出发地和目的地航线的最便宜运费,并告知客户。
但是,根据行程,有时可能无法使用船舶旅行。这种情况下,需要告诉客户“无法使用船舶旅行”。此外,在JOI国,连接岛屿之间的新船舶陆续开始运营,你将随时收到这些信息。在回复客户时,必须重点参考最新信息。
当输入提供客户订单表或新开始运营的船舶航运信息时,请创建一个程序来生成对客户的回复。
另外,输入示例 1 和输出示例 1 的执行情况以图 1 显示。
入力
输入的 1 在线 2 整数 n, k (1 \leqq n \leqq 100,1 \leqq k \leqq 5\,000) 中有说明。这是指岛屿的数量为 n 在岛上,输入表示为 k + 1 行。
i + 1 行目 (1 \leqq i \leqq k) 中,3 个或 4 个整数以空格分隔书写。
- 当第一个数字为 0 时,这一行表示顾客的订单票。
这一行中 3 整数 0, a, b (1 \leqq a \leqq n,1 \leqq b \leqq n,a \neq b) 以空格分隔书写。
这表示顾客提交了从岛 a 出发、以岛 b 为目的地的订单票。 - 当第一个数字为 1 时,这一行表示新开始运营的船舶的运营信息。
这一行中 4 整数 1, c, d, e (1 \leqq c \leqq n,1 \leqq d \leqq n,c \neq d,1 \leqq e \leqq 1\,000\,000) 已书写。
这表示往返岛 c 和岛 d 的船舶新开始运营,该船舶从岛 c 到岛 d 的运输租赁,以及运往 d 到岛 c 的运输租赁,都 e 表示是这样的。
从这一行起的订货单,对于这些订货单,也必须考虑这艘船舶并进行归还处理。
在最初的阶段,假设船舶一艘也没有运营。在输入中,表示船舶运营信息的行是 1\,000 行如下。另外,请注意,在岛与岛之间,有时会有多艘船舶航行。
出力
在输入中,表示订单票的行数 m 记作
输出是
由 m 行组成,
写入一个整数,表示对第i 行目 (1 \leqq i \leqq m) 中,i 订单的回复。
也就是说,
如果可以在第i 订单的出发地和目的地之间转乘多艘船旅行,请填写总票价的最小值。如果无法出行,
写入-1 。
下图显示了
入力例 1
3 8 1 3 1 10 0 2 3 1 2 3 20 1 1 2 5 0 3 2 1 1 3 7 1 2 1 9 0 2 3
出力例 1
-1 15 12
另外,输入示例 1 和输出示例 1 船如何开始运营以及对客户订单的回复。 如下图所示 1 。


入力例 2
5 16 1 1 2 343750 1 1 3 3343 1 1 4 347392 1 1 5 5497 1 2 3 123394 1 2 4 545492 1 2 5 458 1 3 4 343983 1 3 5 843468 1 4 5 15934 0 2 1 0 4 1 0 3 2 0 4 2 0 4 3 0 5 3
出力例 2
5955 21431 9298 16392 24774 8840