#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Title

### Problem Statement

You are given a tree with `N` vertices.

Here, a *tree* is a kind of graph, and more specifically, a connected undirected graph with `N-1` edges, where `N` is the number of its vertices.

The `i`-th edge `(1≤i≤N-1)` connects Vertices `a _{i}` and

`b`, and has a length of

_{i}`c`.

_{i}You are also given `Q` queries and an integer `K`. In the `j`-th query `(1≤j≤Q)`:

- find the length of the shortest path from Vertex
`x`and Vertex_{j}`y`via Vertex_{j}`K`.

### Constraints

`3≤N≤10`^{5}`1≤a`_{i},b_{i}≤N (1≤i≤N-1)`1≤c`_{i}≤10^{9}(1≤i≤N-1)- The given graph is a tree.
`1≤Q≤10`^{5}`1≤K≤N``1≤x`_{j},y_{j}≤N (1≤j≤Q)`x`_{j}≠y_{j}(1≤j≤Q)`x`_{j}≠K,y_{j}≠K (1≤j≤Q)

### Input

Input is given from Standard Input in the following format:

Na_{1}b_{1}c_{1}:a_{N-1}b_{N-1}c_{N-1}QKx_{1}y_{1}:x_{Q}y_{Q}

### Output

Print the responses to the queries in `Q` lines.

In the `j`-th line `j(1≤j≤Q)`, print the response to the `j`-th query.

### Sample Input 1

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

### Sample Output 1

3 2 4

The shortest paths for the three queries are as follows:

- Query
`1`: Vertex`2`→ Vertex`1`→ Vertex`2`→ Vertex`4`: Length`1+1+1=3` - Query
`2`: Vertex`2`→ Vertex`1`→ Vertex`3`: Length`1+1=2` - Query
`3`: Vertex`4`→ Vertex`2`→ Vertex`1`→ Vertex`3`→ Vertex`5`: Length`1+1+1+1=4`

### Sample Input 2

7 1 2 1 1 3 3 1 4 5 1 5 7 1 6 9 1 7 11 3 2 1 3 4 5 6 7

### Sample Output 2

5 14 22

The path for each query must pass Vertex `K=2`.

### Sample Input 3

10 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 1 1 9 10

### Sample Output 3

17000000000

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 28 | 1s | 256MB | Average |

2 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o paththruk -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512