Gi 是一个淘气的孩子，他经常做一些奇怪的事情。因此，他的父亲决定和他玩一个游戏。

Gi 的父亲是一位资深魔术师，他将 Gi 和 Gi 的拖鞋传送进了一个迷宫。为了简化问题，我们将迷宫看作一棵以节点 $1$ 为根的树。Gi 最初位于节点 $s$，他的拖鞋位于节点 $t$。在树中，经过任意两个节点之间的边需要消耗 $w$ 单位的能量。

Gi 也是一位小魔术师！如果两个节点之间的深度差等于 $k$，他可以使用魔法传送至另一个节点。也就是说，如果两个节点 $u, v$ 满足 $|dep_u - dep_v| = k$，那么 Gi 可以从 $u$ 传送到 $v$，或者从 $v$ 传送到 $u$。但每次使用魔法时，他需要消耗 $p$ 单位的能量。注意，他可以使用任意多次魔法。

Gi 想要以最小的能量消耗拿到他的拖鞋。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 5$)。

接下来是各测试用例的描述。

第一行包含一个整数 $n$ —— 树的节点数，$2 \le n \le 10^6$。

接下来的 $n - 1$ 行，每行包含 3 个整数 $u, v, w$，表示节点 $u$ 和 $v$ 之间有一条边，经过该边消耗 $w$ 单位能量，$1 \le u, v \le n, 1 \le w \le 10^6$。

下一行包含两个整数 $k, p$，$1 \le k \le \max_{u \subseteq V} (dep_u), 0 \le p \le 10^6$。

最后一行包含两个正整数 $s, t$，表示 Gi 和拖鞋的位置，$1 \le s, t \le n$。保证 $s \neq t$。

输出格式

对于每个测试用例：

输出一行一个整数 —— Gi 所需的最小能量消耗。

样例

输入 1

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

输出 1

12

说明

样例 1：Gi 可以从节点 $6$ 到节点 $1$ 消耗 $2$ 单位能量。然后他从节点 $1$ 传送到节点 $2$ 消耗 $8$ 单位能量。最后，他从节点 $2$ 到节点 $5$ 消耗 $2$ 单位能量。 总消耗 $= 2 + 8 + 2 = 12$。