提示: 欢迎访问OurACM平台。
Problem 2082 过路费

Accept: 829    Submit: 2659
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

有n座城市,由n-1条路相连通,使得任意两座城市之间可达。每条路有过路费,要交过路费才能通过。每条路的过路费经常会更新,现问你,当前情况下,从城市a到城市b最少要花多少过路费。

Input

有多组样例,每组样例第一行输入两个正整数n,m(2 <= n<=50000,1<=m <= 50000),接下来n-1行,每行3个正整数a b c,(1 <= a,b <= n , a != b , 1 <= c <= 1000000000).数据保证给的路使得任意两座城市互相可达。接下来输入m行,表示m个操作,操作有两种:一. 0 a b,表示更新第a条路的过路费为b,1 <= a <= n-1 ; 二. 1 a b , 表示询问a到b最少要花多少过路费。

Output

对于每个询问,输出一行,表示最少要花的过路费。

Sample Input

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

Sample Output

1 2

Source

FOJ有奖月赛-2012年4月(校赛热身赛)

Submit  Back  Status  Discuss