CF343E Pumping Stations

疯狂科学家 Mike 应聘了一份工作。他的任务是管理一套水泵站系统。 该系统由 $n$ 个水泵站组成，编号为 $1$ 到 $n$。有些水泵站之间通过双向管道相连，水可以双向流动（但同一时间只能朝一个方向流动）。每一条管道都有其带宽，即每小时最多可以通过多少升水。每个水泵站可以通过管道将接收到的部分水输送到其他站点，但要求在一小时内流入该站点的水量等于流出该站点的水量。 Mike 的工作是负责在站点之间输送水。在一小时内，可以按照上述规则通过管道（可能经过其它站点）将一定量的水从站点 $a$ 输送到站点 $b$。在此期间，其他站点的水禁止流入站点 $a$，也禁止从站点 $b$ 流出水。然而，任意数量的水都可以从站点 $a$ 流出，或者流入站点 $b$。如果在一小时内有 $x$ 升水流出站点 $a$，Mike 的工资将增加 $x$ bollars。 根据合同，Mike 需要工作 $n-1$ 天以获得报酬。第一天，他选择两个站点 $v_1$ 和 $v_2$，在一小时内将一定量的水从 $v_1$ 输送至 $v_2$。接下来，第 $i$ 天，Mike 选择一个此前未选择过的站点 $v_{i+1}$，并在一小时内将一定量的水从 $v_i$ 输送到 $v_{i+1}$。第 $i$ 天输送的水量不依赖于第 $i-1$ 天的输送量。 为了获得最大的报酬，Mike 需要让工资尽可能高。请帮助 Mike 找到一种站点编号排列 $v_{1},v_{2},...,v_{n}$，使他能获得最多的工资。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $m$（$2 \leq n \leq 200$，$1 \leq m \leq 1000$），表示系统中水泵站和管道的数目。接下来的 $m$ 行中的第 $i$ 行包含三个用空格分隔的整数 $a_i$，$b_i$ 和 $c_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq c_i \leq 100$），表示第 $i$ 条管道连接的两个水泵站编号及其带宽。保证任意两个站点之间至多有一条管道，并且任意两个站点之间都存在管道路径。

第一行输出一个整数，表示 Mike 能获得的最大工资。 第二行输出 $n$ 个用空格隔开的整数，表示一种符合条件的水泵站编号排列 $v_{1},v_{2},...,v_{n}$。如果存在多种答案，输出任意一种即可。

由 ChatGPT 5 翻译