Diverging Directions
Tag(s):

## Medium

Problem
Editorial
Analytics

You are given a directed weighted graph with n nodes and $2n-2$ edges. The nodes are labeled from 1 to n, while the edges are labeled from 1 to $2n-2$. The graph's edges can be split into two parts.

• The first $n-1$ edges will form a rooted spanning tree, with node 1 as the root. All these edges will point away from the root.
• The last $n-1$ edges will be from node i to node 1, for all $2 \leq i \leq n$.

You are given q queries. There are two types of queries

• $1 i w$: Change the weight of the i-th edge to w
• $2 u v$: Print the length of the shortest path from node u to v

Given these queries, print the shortest path lengths.

### Input Format

The first line of input will contain two integers $n,q$, the number of nodes, and the number of queries, respectively.

The next $2n-2$ integers will contain 3 integers $a_i, b_i, c_i$, denoting a directed edge from node $a_i$ to node $b_i$ with weight $c_i$.

The first $n-1$ of these lines will describe a rooted spanning tree pointing away from node 1, while the last $n-1$ of these lines will have $b_i = 1$.

The next q lines will contain 3 integers, describing a query in the format described in the statement.

### Output Format

For each type 2 query, print the length of the shortest path in its own line.

### Constraints

$2 \leq n \leq 200\,000$

$1 \leq q \leq 200\,000$

$1 \leq a_i, b_i \leq n$

All edge weights will be between 1 and $10^6$.

The edges $(a_1,b_1), (a_2,b_2), \ldots (a_{n-1},b_{n-1})$ will describe a rooted spanning tree pointing away from node 1.

$b_j = 1$ for $n \leq j \leq 2n-2$.

$a_n, a_{n+1}, \ldots, a_{2n-2}$ will be distinct and between 2 and n.

SAMPLE INPUT
5 9
1 3 1
3 2 2
1 4 3
3 5 4
5 1 5
3 1 6
2 1 7
4 1 8
2 1 1
2 1 3
2 3 5
2 5 2
1 1 100
2 1 3
1 8 30
2 4 2
2 2 4

SAMPLE OUTPUT
0
1
4
8
100
132
10
Explanation

.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

IndiaHacks 2017: Programming [Wave 2.0- Eliminator]

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Arrays
• Math > Combinatorics
• Math > Combinatorics