7598: Jump

You are given a rooted tree with n nodes, each edge of the tree has a weight, the nodes of the tree are numbered from 1 to n , the root of the tree is rt .

You are also given an array a with n elements.

Define dep(x) as the sum of weight of edges on the simple path between rt and x .

Define fa(x) as the father of node x , especially, we define fa(rt)=rt .

There are m operations of two types:

`1 l r`: for each i that satisfies l≤i≤r , ai:=fa(ai) .

`2 l r`: for each i that satisfies l≤i≤r , output the minimum dep(ai) .

The input contains several test cases, and the first line contains a single integer T , the number of test cases.

For each test case:

The first line contains three integers n,m,rt .

For the following n−1 lines, each line contains three integers u,v,d , which means that there is an edge between u,v , the weight of which is d .

The next line contains n integers, the ith integer is ai .

For the following m lines, each line contains three integers opt,l,r , which means that there is a operation of type opt for l,r .

1≤T≤4 , 1≤n,m≤2⋅105 , the weight of edge is an integer in range [0,109] .

For each operation that opt=2 , output one line representing the answer.

4
5 1 5
2 5 4
1 5 4
3 2 1
4 2 3
3 4 3 2 5
2 3 3
6 2 1
6 1 1
2 1 1
4 2 3
5 4 2
3 2 1
2 3 6 1 2 6
2 4 6
2 3 3
5 1 5
4 5 3
2 4 2
1 4 2
3 5 3
1 1 5 2 5
2 2 2
5 4 3
2 3 1
1 2 4
5 2 2
4 5 4
1 4 1 1 4
2 2 5
1 1 5
2 2 2
1 1 4

5
0
1
5
5
3