SP26788 SHILL - Tiho Brdo

在中世纪的小镇 Silent Hill，住着一个叫 Glutton 的怪物，专门恐吓镇民。许多骑士尝试过消灭它，但都没能幸存下来。 有一天，一位名叫 Davis 的勇敢建筑师决定向这个怪物发起挑战。他发现 Glutton 实际上是由许多相互连接的「部分」组成的，每一个部分可以「控制」其他部分。Glutton 拥有一个「大脑」，即一个不被其他部分控制的特殊部分。此外，它还有一个或多个「爪子」，即不控制任何其他部分的部分。每个爪子都有且只有一条由大脑（可能通过多个中介）控制的路径。如果 Davis 成功地切断大脑与所有爪子之间的联系，怪物将变得无害。 Davis 运用他的项目技能，发现可以给 Glutton 的每条直接连接 $x \to y$ 分配一个需要切断的力量 $w_{xy}$。他希望投入**最小的总力量**来断开大脑和所有爪子的连接，因此对需要切断的连接顺序十分感兴趣——这些连接应该按照**从左到右**的顺序被选择。如果有多个可行方案，Davis 希望早期的能量消耗更小，也就是说，他想找到**字典序最小**的切断方案。 为了赢得击败 Glutton 后的荣誉和镇上居民的赞美声「谢谢你，勇敢的 Davis！」，Davis 急于找到解决方案，请求你帮忙计算。

第一行包含一个整数 $n$，表示 Glutton 的部分总数量。其中，ID 为 1 的部分总是代表大脑。而后给出每个部分的描述，从大脑到第 $n$ 个部分，顺序如下： - 第一行是一个整数 $m_i$，表示当前部分直接控制的其他部分的数量。 - 如果 $m_i = 0$，则当前部分是一个爪子。 - 否则，第二行包含 $m_i$ 个整数，描述当前部分直接控制的部分的索引，顺序为**从左到右**。 - 第三行包含 $m_i$ 个整数，分别表示切断每个控制连接所需的力量。

输出的第一行是一个整数，表示 Glutton 变得无害所需的最小总力量。第二行输出按照**从左到右**顺序排列的，需要切断的每个连接的力量序列，该序列应满足**字典序最小**的要求。序列中的各个元素之间用一个空格分隔。 **本翻译由 AI 自动生成**