SP10452 CAPRICA - Caprica Cities

Caprica 是十二个殖民星球之一，但已被人类制造、后来反叛的机器人 cylon 完全摧毁。在被攻陷之前，Gaius Baltar 博士面临了这样一个问题：Caprica 由 $N$ 座城市组成，编号从 $0$ 到 $N-1$，这些城市通过 $M$ 条双向道路相连，每对城市之间都有路径可以到达。我们需要从中选出两个不相交且非空的城市子集 $X$ 和 $Y$，找到从 $X$ 中的任意城市 $x$ 到 $Y$ 中的任意城市 $y$ 的最短路径。这里的路径长度是指路径上所有道路长度的总和。

每个测试用例由多行数据构成。第一行包含四个整数 $N, M, A, B$，分别表示城市数量（$2 < N \leq 200$），道路数量（$1 \leq M \leq 10000$），集合 $X$ 中城市的数量（$2 \leq A < N$），以及集合 $Y$ 中城市的数量（$B = N - A$）。第二行列出 $X$ 集合中的 $A$ 个城市编号，第三行列出 $Y$ 集合中的 $B$ 个城市编号。接下来的 $M$ 行，每行包含三个整数 $u, v, d$，表示城市 $u$ 和城市 $v$ 之间存在一条距离为 $d$ 的道路（$1 \leq u, v < N$，$1 \leq d \leq 1000$）。输入的最后，以一行四个零结尾表示测试用例的终止。

对于每个测试用例，输出一行，表示从集合 $X$ 中的某城市到集合 $Y$ 中某城市的最短路径长度。 **本翻译由 AI 自动生成**