题目描述

在 JOI 国有 $n$ 座岛屿，每座岛屿按从 $1$ 到 $n$ 编号。目前，JOI 国正在推进连接各岛屿之间的航线网络建设。

你在一家经营船票的票务中心工作。在 JOI 国，有许多人希望乘船以尽可能低廉的价格在岛屿之间旅行，他们会将出发地和目的地填写在订单上并寄给你。

你的工作是在收到客人的订单后，立即计算出通过换乘若干艘船连接出发地和目的地的航线中最便宜的票价，并告知客人。但是，根据行程的不同，有时可能无法乘船旅行。此时，需要告知客人“无法乘船旅行”。此外，在 JOI 国，连接岛屿与岛屿的新船只正陆续开始运营，你会随时收到这些信息。在回复客人时，必须留意最新的运营信息。

当给定客人的订单以及新开始运营的船只的运营信息作为输入时，请编写程序求出对客人的回复。

输入格式

输入的第 $1$ 行写有 $2$ 个整数 $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$)。这表示岛屿的数量为 $n$ 座，输入共由 $k + 1$ 行组成。第 $(i + 1)$ 行 ($1 \le i \le k$) 中写有以空格分隔的 $3$ 个或 $4$ 个整数。

• 当第一个数字为 $0$ 时，该行表示客人的订单。该行写有以空格分隔的 $3$ 个整数 $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$)。这表示客人寄来了一张以岛屿 $a$ 为出发地、以岛屿 $b$ 为目的地的订单。
• 当第一个数字为 $1$ 时，该行表示新开始运营的船只的运营信息。该行写有 $4$ 个整数 $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$)。这表示一艘往返于岛屿 $c$ 和岛屿 $d$ 之间的船只新开始运营，且该船只从岛屿 $c$ 到岛屿 $d$ 的票价与从岛屿 $d$ 到岛屿 $c$ 的票价均为 $e$。对于该行之后的订单，在回复时必须也将这艘船考虑在内。

在初始阶段，有 $0$ 艘船在运营。在输入中，表示船只运营信息的行数不超过 $1000$ 行。另外请注意，在两座岛屿之间可能会有多艘船只运营。

输出格式

设输入中表示订单的行数为 $m$。输出由 $m$ 行组成，在第 $i$ 行 ($1 \le i \le 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

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