#213392. [NOI2025] 机器人

NOI2025 正在绍兴举办，小 Y 为闭幕式表演制作了一个机器人并打算操控它从仓库走到礼堂。

绍兴的道路系统可以简化为 个路口以及连接这些路口的 条 单行道路，且每条道路有一定的长度。为了方便将道路系统录入机器人的芯片，小 Y 对每一个路口连接的所有道路进行了编号。具体而言，若有 条道路以路口 为起点，则这 条道路会被小 Y 按照某种顺序编号为 ，分别称作以 为起点的第 条道路。

小 Y 的机器人内部有一个参数 。给定参数 的上限 与修改费用 。小 Y 将按照如下规则设置与修改机器人的参数：

• 初始时，小 Y 将参数 设置为 。
• 在 任意时刻，小 Y 可以远程控制机器人修改参数：
  • 若 ，则小 Y 可以花费 的费用将 增加 ，即 ；
  • 若 ，则小 Y 可以花费 的费用将 减少 ，即 。

初始时，小 Y 的机器人位于机器人仓库，即路口 。当机器人位于路口 时，记以路口 为起点的第 条道路的终点为 ，道路长度为 ，则小 Y 可以花费 的费用操控机器人从 走到 。特别地，若以路口 为起点的道路不足 条，则小 Y 无法操控机器人走动。

小 Y 并不知道闭幕式表演所在的礼堂位于哪个路口，因此他需要对每个路口都做好准备。请你帮助他求出将机器人从仓库移动到每个路口所需费用的最小值。

输入的第一行包含一个非负整数 ，表示测试点编号。 表示该测试点为样例。

输入的第二行包含三个正整数 ，分别表示路口数量、道路数量与参数 的上限。

输入的第三行包含 个非负整数 ，表示增加参数 的费用。

输入的第四行包含 个非负整数 ，表示减少参数 的费用。

输入的第 （）行包含若干个正整数，其中第一个非负整数 表示以路口 为起点的道路数量，接下来 个正整数 ，表示以路口 为起点的道路，其中 （）分别表示编号为 的道路的终点与长度。

输出一行 个整数，其中第 （）个数表示小 Y 将机器人从仓库移动到路口 所需费用的最小值。特别地，若小 Y 无法将机器人从仓库移动到该路口，则输出 。

样例输入 1

0
5 6 3
2 4
1 1
3 2 5 3 1 4 2
1 3 2
2 1 2 4 1
0
0

样例输出 1

0 5 3 4 -1

样例 1 解释

小 Y 可以按照以下方案将机器人分别从仓库移动到路口 ：

• 对于路口 ：小 Y 的机器人初始时即位于路口 ，因此所需费用为 。
• 对于路口 ：小 Y 操控机器人沿以路口 为起点的第 条道路走到路口 ，所需费用为 。
• 对于路口 ：小 Y 将参数 增加 ，然后操控机器人沿以路口 为起点的第 条道路走到路口 ，所需费用为 。
• 对于路口 ：小 Y 将参数 增加 ，然后操控机器人沿以路口 为起点的第 条道路走到路口 ，再操控机器人沿以路口 为起点的第 条道路走到路口 ，所需费用为 。

可以证明，上述移动方案的所需费用均为最小值。

• 对于路口 ：由于小 Y 无法将机器人移动到路口 ，因此输出 。

样例 2

见选手目录下的 robot/robot2.in 与 robot/robot2.ans。

该样例满足测试点 的约束条件。

样例 3

见选手目录下的 robot/robot3.in 与 robot/robot3.ans。

该样例满足测试点 的约束条件。

样例 4

见选手目录下的 robot/robot4.in 与 robot/robot4.ans。

该样例满足测试点 的约束条件。

样例 5

见选手目录下的 robot/robot5.in 与 robot/robot5.ans。

该样例满足测试点 的约束条件。

数据范围

对于所有测试数据，保证：

• ，；
• 对于所有 ，均有 ；
• 对于所有 ，均有 ；
• 对于所有 ，均有 ，且 ；
• 对于所有 ，，均有 ，。

::cute-table{tuack}

• 特殊性质 A：保证 且 。
• 特殊性质 B：保证对于所有 ，，均有 。
• 特殊性质 C：保证至多存在 10 个 满足 。

附加文件来自于 QOJ。