国王走了。国王统治后,王国的所有道路都破旧不堪,需要维修。国王的三个孩子,阿德里安、比阿特丽斯和塞西莉亚,正在瓜分王国。
Adrian 和 Beatrice 彼此不喜欢,也不打算在未来维持任何关系。塞西莉亚和他们两人的关系都很好。而且,大部分王国工人都支持塞西莉亚,所以她有更好的资源和更多的机会来修复基础设施和发展经济。
塞西莉亚提议将王国分为三个区:A(阿德里安)、B(贝阿特丽斯)和C(塞西莉亚),并让阿德里安和贝阿特丽斯协商并选择他们想要在其区中的任何城镇,并就他们希望如何将王国分为三个区达成一致。
Adrian 的城堡位于镇 $$$a$$$,Beatrice 的城堡位于镇 $$$b$$$。因此,阿德里安和比阿特丽斯希望他们的城堡分别位于 A 区和 B 区。塞西莉亚没有城堡,所以C区不能有城镇。
Adrian 和 Beatrice 遇到了问题。当他们选择城镇时,他们将不得不支付道路的维修费用。
修复长度 $$$l$$$ 的道路的成本为 $$$2l$$$ 金币。然而,阿德里安和比阿特丽斯不必承担所有的维修费用。他们承担的长度为 $$$l$$$ 的道路的维修费用取决于它连接哪些城镇:
- 对于 A 区内两个城镇之间的道路,Adrian 必须支付 $$$2l$$$ 金币;
- 对于 B 区内两个城镇之间的道路,Beatrice 必须支付 $$$2l$$$ 金币;
- A区和C区城镇之间的道路,Adrian需要支付$$$l$$$金币,Cecilia承担剩余费用;
- 对于 B 区和 C 区城镇之间的道路,Beatrice 必须支付 $$$l$$$ 金币,Cecilia 承担剩余费用。
连接A区和B区城镇的道路不会被修复,因为阿德里安和比阿特丽斯不打算使用它们,所以没有人支付费用。塞西莉亚自己会修理连接C区城镇的道路,所以阿德里安和贝阿特丽斯也不会承担修理费用。
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 \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$$$ 个城镇应属于的地区。
如果存在几种最便宜的分割王国的方法,请打印其中任何一种。
示例
输入复制
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
输出复制
16 ABBCBA
注意
下图说明了示例。 Adrian 和 Beatrice 不为虚线道路付费,他们为粗线道路支付 $$$2l$$$ ,为实线道路支付 $$$l$$$ 。
因此总成本为 $$$2 \cdot 5 + 3 + 3 = 16$$$。
阿德里安和比阿特丽斯的城堡位于大胆的城镇中。