最短距离
题目描述
给出一个 $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$ 输出查询的结果。
输入输出样例
输入样例 #1
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
输出样例 #1
13
12
26
16
说明
![Luogu](https://cdn.luogu.com.cn/upload/pic/37934.png)
对于 $100\%$ 的数据,保证 $z\in [0,5000]$。