CF1666K Kingdom Partition

国王已去世。在国王统治期间，王国中的所有道路都破败不堪，需要修复。国王的三个孩子，Adrian，Beatrice 和 Cecilia，正在将王国瓜分给他们自己。 Adrian 和 Beatrice 彼此不喜欢对方，并且不打算在未来保持任何联系。Cecilia 分别与他们两个关系良好。此外，王国的大多数工人都支持 Cecilia，因此她拥有更好的资源和更多的机会修复基础设施和发展经济。 Cecilia 提议将王国分为三个区域：A区（给 Adrian）、B区（给 Beatrice）和 C区（给 Cecilia），并让 Adrian 和 Beatrice 协商并选择他们想要放在各自区域内的城镇，并达成对如何将王国分割成三个区域的协议。 Adrian 的城堡位于城镇 A，而 Beatrice 的城堡位于城镇 B。因此，Adrian 希望他的城堡位于 A 区，而 Beatrice 希望她的城堡位于 B 区。Cecilia 没有城堡，所以 C 区可以不包含任何城镇。 Adrian 和 Beatrice 面临一个问题。当他们选择了城镇之后，他们将需要支付道路修复的费用。 修复长度为 $l$ 的道路所需费用为 $2\cdot l$ 金币。然而，Adrian 和 Beatrice 并不需要承担所有的修复费用。他们所需承担的长度为 $l$ 的道路修复费用取决于它连接的城镇： - 对于连接 A 区内的两个城镇之间的道路，Adrian 需要支付 $2\cdot l$ 金币的费用。 - 对于连接 B 区内的两个城镇之间的道路，Beatrice 需要支付 $2\cdot l$ 金币的费用。 - 对于连接 A 区和 C 区之间的城镇的道路，Adrian 需要支付 $l$ 金币的费用，剩下的费用由Cecilia承担。 - 对于连接 B 区和 C 区之间的城镇的道路，Beatrice 需要支付 $l$ 金币的费用，剩下的费用由Cecilia承担。 连接 A 区和 B 区的城镇之间的道路将不会修复，因为 Adrian 和 Beatrice 没有打算使用它们，所以没有人为它们支付费用。Cecilia 将自己修复连接 C 区内的城镇的道路，因此 Adrian 和 Beatrice 也不需要承担修复费用。 Adrian 和 Beatrice 希望尽量减少在道路修复上的总花费。找到他们将王国分割成三个区域的最便宜的方式。

第一行包含两个整数 $n$ 和 $m$ ——城镇的数量和王国中道路的数量 $(2\le n\le 1000;0 \le m\le 2000)$。 第二行包含两个整数 $a$ 和 $b$，表示必须位于 A 区和 B 区的城镇 $a$ 和 $b$ $(1\le a,b\le n;a\ne b)$。 接下来 $m$ 行描述了王国中的道路。第 $i$ 行包含三个整数 $u_i$，$v_i$，$l_i$，表示一条在 $u_i$ 和 $v_i$ 之间长度为 $l_i$ 的道路 $(1\le u_i,v_i\le n;u_i\ne v_i;1\le l_i\le 10^9)$。 两个城镇之间之多只有一条道路（即无重边）。

第一行输出一个整数——Adrian 和 Beatrice 修复道路的最小总费用。 第二行输出一个由 $n$ 个字符 'A'、'B' 和 'C' 组成的字符串，其中第 $i$ 个字符表示第 $i$ 个城镇应属于的区域。 如果存在多种最便宜的王国分割方式，可以输出其中任意一种。 ### **说明/提示** 以下图片说明了示例情况。Adrian 和 Beatrice 不支付虚线道路的费用，他们支付 $2\cdot l$ 的费用用于修复加粗道路，以及 $l$ 的费用用于修复实线道路。 所以总花费是 $2\cdot 5 + 3 + 3 = 16$； Adrian 和 Beatrice 的城堡位于图中加粗的城镇。

The following picture illustrates the example. Adrian and Beatrice don't pay for the dashed roads, they pay $ 2l $ for the bold roads, and $ l $ for the solid roads. So the total cost is $ 2 \cdot 5 + 3 + 3 = 16 $ . The castles of Adrian and Beatrice are located in bold towns.