题目背景

西伯利亚北部的寒地，坐落着由 $N$ 个小岛组成的岛屿群，我们把这些小岛依次编号为 $1$ 到 $N$。

题目描述

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

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

输入格式

输入共 $M+1$ 行。

第一行有两个整数 $N$ 和 $M$，分别表示小岛的数与总操作数。

接下来的 $M$ 行，每行表示一个操作，格式如下：

0 s t：表示询问从 $s$ 号小岛到 $t$ 号小岛的最短用时（$1\le s\le n,~ 1\le t\le n,~ s\neq t$）。

1 u v e：表示新增了一条从 $u$ 号小岛到 $v$ 号小岛，用时为 $e$ 的双向航线（$1\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\%$ 的数据，$N\le 5$ 且 $M\le 30$。

对于 $40\%$ 的数据，$N\le 20$ 且 $M\le 200$。

对于 $60\%$ 的数据，$N\le 80$ 且 $M\le 500$。

对于 $80\%$ 的数据，$N\le 100$ 且 $M\le 2500$。

对于 $100\%$ 的数据，$N\le 100$ 且 $M\le 5000$。