6876：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 \le i \le r$, $a_i := fa(a_i)$.

`2 l r`: for each $i$ that satisfies $l \le i \le r$, output the minimum $dep(a_i)$.

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 $a_i$.

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\le T \le 4$, $1\le n,m\le 2\cdot 10^5$, the weight of edge is an integer in range $[0,10^9]$.

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