#P2683. 小岛

小岛

题目背景

西伯利亚北部的寒地,坐落着由 NN 个小岛组成的岛屿群,我们把这些小岛依次编号为 11NN

题目描述

起初,岛屿之间没有任何的航线。后来随着交通的发展,逐渐出现了一些连通两座小岛的航线。例如增加一条在 uu 号小岛与 vv 号小岛之间的航线,这条航线的用时为 ee。那么沿着这条航线,uu 号小岛上的人可以前往 vv 号小岛,同样的 vv 号小岛上的人也可以前往 uu 号小岛,其中沿着这一条航线花费的时间为 ee

同时,随着旅游业的发展,越来越多的人前来游玩。那么两个小岛之间的最短路径是多少便成为了饱受关注的话题。

输入格式

输入共 M+1M+1 行。

第一行有两个整数 NNMM,分别表示小岛的数与总操作数。

接下来的 MM 行,每行表示一个操作,格式如下:

0 s t:表示询问从 ss 号小岛到 tt 号小岛的最短用时(1sn, 1tn, st1\le s\le n,~ 1\le t\le n,~ s\neq t)。

1 u v e:表示新增了一条从 uu 号小岛到 vv 号小岛,用时为 ee 的双向航线(1un, 1vn, uv, 1e1061\le u\le n, ~1\le v\le n,~ u ≠ v,~ 1\le e\le 10^6)。

输出格式

输出针对每一次询问,单独输出一行。

对于每一组询问来说,如果不存在可行的道路,则输出 -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
15
12
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
5955
21431
9298
16392
24774
8840

提示

对于 20%20\% 的数据,N5N\le 5M30M\le 30

对于 40%40\% 的数据,N20N\le 20M200M\le 200

对于 60%60\% 的数据,N80N\le 80M500M\le 500

对于 80%80\% 的数据,N100N\le 100M2500M\le 2500

对于 100%100\% 的数据,N100N\le 100M5000M\le 5000