[AdditionalFile5263.zip](file://AdditionalFile5263.zip?type=additional_file)

#5263. 「NOISG 2024 Final」Shops

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2024 Final T1. Shops

詹姆斯是优兰国的市长，该国包含 $n$ 个城市，通过 $m$ 条双向道路连接，道路距离不全相同。可以仅通过这些道路从任意城市到达其他任意城市。注意，同一对城市之间可能存在多条道路。

每个城市可以开设兔子商店或鸭子商店，但不能同时开设两者。每个城市的居民希望收集两种动物。城市的不便度定义为到最近的兔子商店和到最近的鸭子商店的距离中的最大值。

詹姆斯尚未建设商店，需要你的帮助选择在哪些城市建设哪种商店，以最小化所有城市不便度的最大值。

输入格式

程序需从标准输入读取数据。

输入的第一行包含两个整数 $n, m$。

接下来的 $m$ 行，每行包含三个整数 $u[i], v[i], w[i]$，表示连接城市 $u[i]$ 和 $v[i]$ 的一条道路，距离为 $w[i]$。

输出格式

程序需向标准输出输出结果。

第一行应为所有城市不便度的最小可能最大值。

第二行应为一个长度为 $n$ 的字符串，包含字符 B 或 D，其中第 $i$ 个字符表示在第 $i$ 个城市选择建设兔子商店（B）或鸭子商店（D）。如果存在多种建设方式使得最大不便度等于第一行所述的值，任意一种均可接受。

样例 1

输入

3 3
1 2 3
2 3 1
1 3 2

输出

2
BBD

在此分配中，城市 $1$ 和 $2$ 开设兔子商店，城市 $3$ 开设鸭子商店。因此，各城市的不便度为 $[2,1,1]$，最大值为城市 $1$ 的 $2$。

这个样例满足子任务 $1,5$ 的限制。

样例 2

输入

5 6
3 2 3
4 2 1
5 3 9
1 3 5
1 4 2
2 3 1

输出

9
DBDDB

在此分配中，各城市的不便度为 $[3,1,1,1,9]$，最大值为城市 $5$ 的 $9$。

这个样例满足子任务 $1,5$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq n, m \leq 500000$
• $1 \leq u[i], v[i] \leq n$
• $1 \leq w[i] \leq 10^{9}$
• 仅通过道路可从任意城市到达其他任意城市。

详细子任务附加限制及分值如下表所示：