问题

在JOI国家，有$n$个岛屿，每个岛屿都被编号为1到$n$。目前，JOI国家正在努力建设连接各个岛屿的航线网络。

您是一家售票中心的工作人员，负责处理船票。JOI国家有很多人希望通过乘船尽可能廉价地旅行岛与岛之间，他们会填写出发地和目的地的订单并发送给您。

您的工作是在收到客户订单后，通过乘坐一些船只在出发地和目的地之间的航线中计算出最便宜的票价，并告知客户。

但是，根据旅程不同，有时无法乘船旅行。这种情况下，您需要告知客户“无法使用船只进行旅行”。此外，JOI国家正在陆续开通连接岛屿之间的新船只，并且您会随时收到相关信息。在回复客户时，您必须注意最新的信息。

请编写一个程序，当给定客户订单或新船舶的运营信息时，求出对客户的回复。

注意，在输入示例1和输出示例1中，已经用图1表示了执行状态。

输入

输入的第一行包含两个整数$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$张客户订单的回复。 换句话说，如果可以通过乘坐一些船只在出发地和目的地之间旅行，则写下票价总和的最小值。如果无法旅行，则写$-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中描绘如下：

输入示例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