Developing Cities

注意

本問題は Python での AC 自体は確認していますが、 Python は PyPy の使用を推奨します。
また、入力の量が多くなる場合があるので、高速な方法で入力を行うことを推奨します。

問題文

$N$ 個の街と $M$ 個の道路が存在します。街にはそれぞれ街 $1$ 、街 $2$ 、$\dots$ 、街 $N$ と名前が割り当てられており、 それぞれの道路も同様に $1$ から $M$ まで番号が割り当てられており、 $i$ 番目の道路は街 $A_i$ から 街 $B_i$ へのみ移動できる距離 $C_i$ の一方通行の道路です。街 $B_i$ から街 $A_i$ へは移動できないことに注意してください。

今、 $Q$ 個のクエリが渡されます。各クエリは以下の $2$ 種類です。

• クエリ $1$ ：街 $D$ から街 $E$ へのみ移動できる距離 $F$ の一方通行の道路を新設する
• クエリ $2$ ：街 $X$ から街 $Y$ への最短距離を求め、出力する（ たどり着けない場合は -1 ）

全てのクエリを順番に処理してください。

制約

• $2 \le N \le 50$
• $1 \le M \le 5 \times 10^5$
• $1 \le A_i,B_i,D,E,X,Y \le N$
• $1 \le C_i,F \le 5 \times 10^6$
• $1 \le Q \le 5 \times 10^3$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

各クエリは以下の形式で与えられる。

出力

クエリ $2$ の答えを出力してください。

入出力例１

5 6
1 2 7
1 3 2
1 4 5
3 5 6
4 5 1
5 2 10
5
2 1 2
2 1 5
1 1 5 2
2 1 2
2 1 5

7
6
7
2

最初、街 $1$ から街 $2$ へは道路 $1$ 、街 $1$ から街 $5$ へは道路 $3$ と道路 $5$ を使うのが最短です。
$3$ 番目のクエリでは、街 $1$ から街 $5$ へ距離 $2$ の道路が新設されるので、街 $1$ から街 $5$ へはこの道路を使った方が距離は短くなります。