#214494. [JOISC 2018] 野猪 / Wild Boar

JOI-kun 是一只生活在 IOI 森林中的野猪，森林中有 个补给站和 条道路。补给站编号为 至 。第 条道路（）双向连接补给站 和 ，JOI-kun 沿该道路往返任一方向均需耗时 小时。从任意补给站出发，均可经由一条或多条道路抵达其他任意补给站。

JOI-kun 不擅长掉头。他不能在道路中途掉头返回刚离开的补给站。此外，当他通过某条道路抵达一个补给站后，不能沿原路立即返回上一个补给站。

每天，JOI-kun 根据 补给计划 在补给站供应食物。每日的补给计划由一个长度为 的补给站序列 组成。他从补给站 开始供应，按顺序访问各补给站，最终在补给站 结束供应。途中允许经过其他补给站。他可能多次在同一个补给站供应食物，但需满足对每个 （），有 。请注意，可能存在他无法执行的补给计划。

初始时，JOI-kun 制定初始补给计划 。在第 天早晨（），他会将计划中第 个值修改为 （即 变为 ），然后按新计划供应食物。修改后，对每个 （），仍满足 。

对于 天内每一天的补给计划，JOI-kun 希望判断他是否能够执行该计划；若可以执行，则求出按该计划供应食物所需的最短时间。

任务

给定 IOI 森林的数据和 JOI-kun 的补给计划，对于 天内每一天的补给计划，编写一个程序，判断他是否能够执行该计划；若可以执行，则求出按该计划供应食物所需的最短时间。

从标准输入读取以下数据：

• 输入第一行包含四个以空格分隔的整数 、、 和 。这表示 IOI 森林中有 个补给站和 条道路，JOI-kun 考虑 天的补给计划，且补给计划由长度为 的序列构成。
• 接下来的 行中，第 行（）包含三个以空格分隔的整数 、 和 。这表示第 条道路双向连接补给站 和 ，JOI-kun 沿该道路往返任一方向均需耗时 小时。
• 接下来的 行中，第 行（）包含一个整数 。这表示初始补给计划为 。
• 接下来的 行中，第 行（）包含两个以空格分隔的整数 和 。这表示 JOI-kun 将在第 天早晨把补给计划中的第 个值修改为 。

向标准输出写入 行。第 行（）应包含 ，若他在第 天无法执行补给计划；否则，输出他能够执行该计划所需的最短时间（单位：小时）。

样例输入 1

3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1

样例输出 1

3

样例输入 2

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

样例输出 2

5
2
3
-1

样例输入 3

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

样例输出 3

38

样例 1 解释

在样例输入 1 中，初始补给计划为 1、2、3。JOI-kun 在第 1 天早晨将该补给计划的第 3 个值修改为 1。因此，第 1 天的补给计划为 1、2、1。

首先，JOI-kun 在补给站 1 供应食物。接着，他使用第 1 条道路从补给站 1 前往补给站 2，并在补给站 2 供应食物。然后，他使用第 2 条道路从补给站 2 前往补给站 3。最后，他使用第 3 条道路从补给站 3 前往补给站 1，并在补给站 1 供应食物。如此执行补给计划共需 3 小时。由于这是可能的最短时间，输出 3。

请注意，JOI-kun 不能按 1 → 2 → 1 的路径移动，因为他不能掉头。

样例 2 解释

在样例输入 2 中，第 1 天的补给计划为 4、1、4。首先，JOI-kun 在补给站 4 供应食物。接着，他使用第 4 条道路从补给站 4 前往补给站 1，并在补给站 1 供应食物。然后，他按顺序使用第 1、2、3、4 条道路，依次经过补给站 1 → 2 → 3 → 1 → 4，并在补给站 4 供应食物。此路径耗时最短。

第 4 天的补给计划为 2、4、2。由于 JOI-kun 无法执行该计划，输出 -1。

数据范围

所有输入数据满足以下条件：

• 。
• 。
• 。
• 。
• （）。
• （）。
• 从任意补给站出发，均可经由一条或多条道路抵达其他任意补给站。
• （）。
• （）。
• （）。
• （）。
• 对每个 （），有 。此外，在每次修改补给计划后，对每个 （），仍满足 。

子任务

共有 4 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [12 分]

• 。
• 。
• 。
• 。
• （）。

子任务 2 [35 分]

• 。
• 。
• 。

子任务 3 [15 分]

• 。

子任务 4 [38 分]

无额外约束。

翻译由 Qwen3-235B 完成