Description

大兵是个淘气的孩子。他经常做一些奇怪的事情。因此，他的父亲决定和他玩一个游戏大兵的父亲是一名高级魔术师，他将大兵和大兵的拖鞋传送到迷宫中。为了简化这个问题，我们将迷宫视为具有节点的树，根植于节点 $1$。大兵最初位于节点 $s$，他的拖鞋位于节点 $t$。在树中，通过两个节点之间的任何边都会消耗 $w$ 点能量。大兵也是一个小魔术师！如果 $u$，$v$ 两个节点之间深度差等于 $k$。也就是说，如果两个节点满足该条件 $|dep_u-dep_v|$ = k，则大兵可以从传送到或从传送到。但每次使用魔法时，他需要消耗 $p$ 点能量。注意，他可以随时使用他的魔法。大兵想用最少的能量来找到他的拖鞋。

Input Format

第一行输入一个正整数 $T$（$1\le T \le 5$），表示有 $T$ 组测试样例.对于每组测试：第一行输入一个整数n（$2 \le n \le 10^6$），表示树的节点的个数。接下来 $n-1$ 行，每行 $3$ 个整数 $u，v，w$，表示节点 $u$ 和节点 $v$ 之间存在一条边，通过这条边需要的花费 $w$ 点能量。接下来一行包含两个整数 $k，p$（$1 \le k \le max_{u\subseteq V(dep_u)},0 \le p \le 10^6$）表示两点之间可以传送的深度和传送所需的花费。最后一行两个整数 $s，t$（$1 \le s \le n, 1 \le t \le n, s \neq t$）表示大兵和拖鞋所在的地方。

Output Format

对于每组测试：输出一行表示大兵找到拖鞋的最小花费。

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

12

Source

Online Judge http://127.0.0.1