Sinchan lives in chefland and loves to visit the houses nearby. There are N houses in city numbered from 1 to N, he lives in house 1. These houses are connected to each other by network of N-1 road, also Sinchan knows another set of N-1 roads which leads to his house from any house. Each road is one way and has unique id labeled from 1 to 2*N-2.
Now for naughtiness of Sinchan he has to pay certain toll tax for passing a road, cost may change after passing of Sinchan. Since Sinchan is smart also so he will choose the path through which he has to pay minimum cost while going from house U to house V.
There are Q queries describing either toll tax changes for particular road or houses U, V for Sinchan. Help Sinchan to save money.
First line contains two integers N and Q. N is number of houses, Q is total queries.
Next 2*N-2 line contains three space separated integer ith
of which has Ui Vi Ci. Denoting toll tax between house U and V is C and road id is i.
Next Q line contains queries of format.
For every query of type 2, output minimum cost Sinchan has to pay.
Constraints2 <= N <= 200000
1 <= Q <= 200000
1 <= Ui, Vi <= N
1 <= Ci <= 1000000
SubtasksSubtask #1 [30 points]: 2 <= N, Q <= 10
Subtask #2 [70 points]: Original constraints
Input: 3 3 1 2 3 1 3 7 2 1 2 3 1 4 2 1 3 1 3 1 2 2 3 Output: 7 8
ExplanationQuery 1: Type 2: dist(1,3) = 7 Query 2: Type 1: update distance of road 3(2->1) to 1 Query 3: Type 2: dist(2,3) = dist(2,1) + dist(1,3) = 1 + 7 = 8
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions