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.