Slipper

Gi is a naughty child. He often does some strange things. Therefore, his father decides to play a game with him.

Gi's father is a senior magician, he teleports Gi and Gi's Slipper into a labyrinth. To simplify this problem, we regard the labyrinth as a tree with $n$ nodes, rooted at node $1$. Gi is initially at node $s$, and his slipper is at node $t$. In the tree, going through any edge between two nodes costs $w$ unit of power.

Gi is also a little magician! He can use his magic to teleport to any other node, if the depth difference between these two nodes equals to $k$. That is, if two nodes $u,v$ satisfying that $|dep_u-dep_v|=k$, then Gi can teleport from $u$ to $v$ or from $v$ to $u$. But each time when he uses magic he needs to consume $p$ unit of power. Note that he can use his magic any times.

Gi want to take his slipper with minimum unit of power.

Each test contains multiple test cases. The first line contains the number of test cases $(1 \le T \le 5)$. Description of the test cases follows.

The first line contains an integer $n$ --- The number of nodes in the tree. $2 \leq n \leq 10^6 $.

The following $n-1$ lines contains 3 integers $u,v,w$ that means there is an edge between nodes $u$ and $v$. Going through this edge costs $w$ unit of power. $1 \leq u,v \leq n,1 \leq w \leq 10^6$.

The next line will contain two separated integers $k, p$. $1 \leq k \leq \max_{u\subseteq V} \left( dep_u \right),0 \leq p \leq 10^6$.

The last line contains two positive integers $s,t$, denoting the positions of Gi and slipper. $1 \leq s \leq n,1 \leq t \leq n$. It is guaranteed the $s \ne t$.

For each test case:

Print an integer in a line --- the minimum unit of power Gi needs.

1
6
6 1 2
3 5 2
2 4 6
5 2 2
5 6 20
3 8
6 5

12

Example1: Gi can go from node 6 to node 1 using 2 units of power. Then he teleports from node 1 to node 2 using 8 units of power. Finally, he goes from node 2 to node 5 using 2 units of power. $Total\ cost = 2+8+2 = 12$

2022“杭电杯”中国大学生算法设计超级联赛（5）