国王去世了。在国王统治结束后，王国所有的道路都年久失修，需要翻新。 国王的三个孩子：Adrian、Beatrice 和 Cecilia，正在瓜分这个王国。 Adrian 和 Beatrice 彼此不和，且计划在未来不保持任何往来。Cecilia 与他们两人的关系都很好。此外，王国的大多数工人都支持 Cecilia，因此她拥有更好的资源和更多的机会来修复基础设施并发展经济。

Cecilia 提议将王国划分为三个区域：A（归 Adrian）、B（归 Beatrice）和 C（归 Cecilia），并让 Adrian 和 Beatrice 商量并选择他们各自想要纳入其区域的城镇，同时就如何将王国划分为三个区域达成一致。

Adrian 的城堡位于城镇 $a$，Beatrice 的城堡位于城镇 $b$。因此，Adrian 和 Beatrice 希望他们的城堡分别位于区域 A 和区域 B 中。Cecilia 没有城堡，因此区域 C 可以不包含任何城镇。

对于 Adrian 和 Beatrice 来说，有一个问题。当他们选择城镇时，他们必须支付道路的维修费用。 修复长度为 $l$ 的道路的费用为 $2l$ 金币。然而，Adrian 和 Beatrice 不需要承担所有的维修费用。他们承担的长度为 $l$ 的道路的维修费用取决于该道路连接的城镇所属的区域：

• 对于连接两个区域 A 内城镇的道路，Adrian 必须支付 $2l$ 金币；
• 对于连接两个区域 B 内城镇的道路，Beatrice 必须支付 $2l$ 金币；
• 对于连接区域 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$ ($1 \le a, b \le n; a \neq 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 \neq v_i; 1 \le l_i \le 10^9$)。 每对城镇之间最多只有一条道路。

输出格式

第一行输出一个整数 —— Adrian 和 Beatrice 支付的最小道路维修总费用。 第二行输出一个由 $n$ 个字符 'A'、'B' 和 'C' 组成的字符串，第 $i$ 个字符表示第 $i$ 个城镇所属的区域。

如果存在多种最廉价的划分方案，输出其中任意一种即可。

样例

输入 1

6 7
1 3
1 2 10
2 3 5
1 3 7
4 5 3
3 6 100
4 6 3
5 6 8

输出 1

16
ABBCBA

说明

下图展示了该样例。Adrian 和 Beatrice 不支付虚线道路的费用，他们为粗线道路支付 $2l$，为实线道路支付 $l$。 因此总费用为 $2 \cdot 5 + 3 + 3 = 16$。 Adrian 和 Beatrice 的城堡位于加粗的城镇中。