题意分析：

• 问题本质：在给定的连通无向图中，找到最小生成树（Minimum Spanning Tree, MST），即边的权重和最小的连通子图。
• 关键约束：
  • 村庄用字母标记（A-Z），数量n∈(1,27)。
  • 道路数为n-1到75条，需处理稀疏图。
  • 必须处理非完全图（并非所有村庄间都有直接道路）。

解题思路：

1. 图表示：

   • 使用邻接表或边列表存储图，推荐边列表（方便排序）。
   • 将字母村庄转换为数字编号（如A=0, B=1...）便于处理。

2. 最小生成树算法选择：

   • Kruskal算法：
     • 按边权升序排序，用并查集（Union-Find）检查环。
     • 时间复杂度O(ElogE)，适合稀疏图（本题E≤75）。
   • Prim算法：
     • 适合稠密图，但本题无需优先选择。

3. 实现步骤：

   • 读取输入，构建边列表。
   • 按权重排序边。
   • 初始化并查集，逐个添加边（跳过成环边），累计权重。