AT_joi2008yo_f 船旅

在 JOI 国，有 $n$ 个岛屿，每个岛屿都有一个从 $1$ 到 $n$ 的编号。这个国家正在积极开展岛屿之间的航线建设。 你在一家船票售卖中心工作。许多客户希望通过船只在岛屿之间用最低的费用旅行，并把他们的出发地和目的地写在订单上交给你。 你的任务是，接到客户的订单后，立即计算出可以从出发地到达目的地的最低票价，并将结果告知客户。 注意，有些行程可能无法通过船只到达，如果是这种情况，你需要告诉客户「无法通过船只旅行」。同时，JOI 国不断有新航线开通，相关信息会实时传递给你，因此你需要根据最新的信息进行回复。 请编写一个程序，根据输入的客户订单和新航线信息，给出每个订单的回复。

第一行输入两个整数 $n, k$ ($1 \leq n \leq 100$，$1 \leq k \leq 5000$)，表示有 $n$ 个岛屿，输入共 $k + 1$ 行。 接下来的 $k$ 行每行包含 3 或 4 个整数，用空格分隔： - 若第一个数字为 0，代表客户订单。 这一行有 3 个整数 $0, a, b$ ($1 \leq a \leq n$，$1 \leq b \leq n$ 且 $a \neq b$)，表示客户希望从岛屿 $a$ 前往岛屿 $b$。 - 若第一个数字为 1，代表新开通的航线信息。 这一行有 4 个整数 $1, c, d, e$ ($1 \leq c \leq n$，$1 \leq d \leq n$ 且 $c \neq d$，$1 \leq e \leq 1,000,000$)，表示岛屿 $c$ 和岛屿 $d$ 之间有一条新航线，其票价为 $e$，且从 $c$ 到 $d$ 和从 $d$ 到 $c$ 的票价相同。在此之后的订单需要考虑这条新航线。 初始时，所有岛屿之间没有航线。输入中用于表示航线的信息行不超过 1000 行。此外，某些岛屿之间可能会有多条航线。

假定输入中表示客户订单的行数为 $m$。输出应包含 $m$ 行，第 $i$ 行 ($1 \leq i \leq m$) 是对第 $i$ 个订单的回复： - 如果可以从订单的出发地通过一些船只中转到达目的地，则输出最低的总票价； - 如果无法通过船只从出发地到目的地，则输出 $-1$。 **本翻译由 AI 自动生成**

### Sample Explanation 1 なお，入力例 $ 1 $ と出力例 $ 1 $ の船舶が運航を開始していく模様と客からの注文票に対する返答を，図 $ 1 $ として以下に図示している． !\[2008-yo-t6.gif\](https://www.ioi-jp.org/joi/2007/2008-yo-prob\_and\_sol/2008-yo-t6/2008-yo-t6.gif) !\[2008-yo-t6.png\](https://img.atcoder.jp/joi2008yo/2008-yo-t6.png) - - - - - -