题目描述

给出一个 $n$ 个点 $n$ 条边的无向连通图。

你需要支持两种操作：

1. 修改 第 $x$ 条边的长度为 $y$ ；

2. 查询 点 $x$ 到点 $y$ 的最短距离。

共有 $m$ 次操作。

输入格式

输入共 $n+m+1$ 行：

第 $1$ 行，包含两个正整数 $n,m$，表示点数即边数，操作次数。

第 $2$ 行到第 $n+1$ 行，每行包含三个正整数 $x,y,z$，表示 $x$ 与 $y$ 间有一条长度为 $z$ 的边。

第 $n+2$ 到 $n+m+1$ 行，每行包含三个正整数 $op,x,y$，表示操作种类，操作的参数（含义见【题目描述】）。

输出格式

对于每次操作 $2$ 输出查询的结果。

4 5
1 2 11
1 3 12
2 3 13
1 4 15
2 2 3
1 2 1
2 2 3
2 2 4
2 3 4

13
12
26
16

提示

对于 $100\%$ 的数据，保证 $z\in [0,5000]$。