该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P4949 最短距离

题目描述

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

你需要支持两种操作：

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

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

共有 $m$ 次操作。

输入格式

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

第 $1$ 行，包含两个正整数 $n,m \ (1 \le n , m \le 10^6)$ ，表示点数即边数，操作次数。

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

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

输出格式

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

输入输出样例 #1

输入 #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