简单题III--复活点

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

RE最近在写一款名叫《我不要娶公主》的RPG游戏(听名字就知道这货单身久
 
了准备FFF),既然是RPG类游戏那么少不了的就是小地图的自动寻路。耿直的RE决定暴力掉这个
 
算法。显然是不行的。所以,这便求到我们这群人。在这个RPG的地图上共有N个复活点,N-1条路
 
,链接整张的地图,保证每两点可达,已知每一条路的长度,战斗就发生在各个复活点和通往复
 
活点的路上。玩家之间的战斗可以改变道路的地形,这便会改变每一条路的长度,那么问题来了
 
。我们如何让玩家得知自己所在的复活点距离自己的目的地多远。

Input

多组输入。每组首先输入两个整数n,m。n为复活点数(n<100001),m为操作数(m<100001)。
 
随后按照书序输入n-1组三个整数u,v,w,表示u复活点与v复活点之间的路程为w。(1<=w<=10000),

最后输入m步操作,每一步操作首先输入一个数字k((k=0||k=1)
 
当k = 0时,输入两个数x,y,表示查询从复活点x到复活点y的总路程。
 
当k = 1时,输入两个数x,y,表示玩家的战斗导致第x条路的长度变成了y。
 

Output

输出玩家查询的从x复活点到y复活点的距离。

Sample Input

3 3
1 2 1
2 3 2
0 1 2
1 2 3
0 2 3

Sample Output

1
3

Hint


Source