← 返回题目列表

Codeforces · 343/E

E. 泵站

中文机器翻译题面 查看原题

疯狂科学家迈克已申请一份工作。他的任务是管理水泵站系统。

系统由n个泵站组成,泵站编号为1到n的整数。一些对的站点通过双向管道连接,水可以通过双向管道向任一方​​向流动(但一次只能流向一个方向)。对于每根管道,您都知道它的带宽——一小时内可以流过的最大水升数。每个泵站可以将一些泵站的进水通过管道泵送到其他泵站,前提是一小时内该泵站的总进水量等于该泵站的总出水量。

迈克负责在站点之间抽水。根据上述规则,在一小时内通过管道(可能通过其他站)从a站到b站可以输送一定数量的水。在此期间,其他站的水不能流入a站,也不能流出b站。然而,任意数量的水都可以流出a站或b站。如果一小时内总共有 x 升水从 a 站流出,那么迈克的工资就多了 x 块。

根据合同,为了获得报酬,Mike 需要工作 n - 1 天。第一天,他选择两个站点 v1 和 v2,并在一小时内将一定量的水从 v1 抽到 v2。接下来,在第 i 天,迈克选择以前从未选择过的站点 vi+1,并从站点 vi 抽出一定量的水到站点 vi+1,持续一小时。他在第 i 天抽出的水量并不取决于第 (i - 1) 天抽出的水量。

迈克需要为他的项目赚取尽可能多的钱。帮助迈克找到这样一个电台编号 v1、v2、...、vn 的排列,这样迈克就能获得尽可能高的薪水。

输入

输入的第一行包含两个空格分隔的整数 n 和 m (2 ≤ n ≤ 200, 1 ≤ m ≤ 1000) — 系统中站和管道的数量。接下来的 m 行中的第 i 行包含三个空格分隔的整数 ai、bi 和 ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) — 相应地,第 i 条管道连接的站数和管道的带宽。保证任意两个站点最多由一根管道连接,并且任意两个站点之间有一条管道路径。

输出

在第一行打印一个整数 - 迈克可以获得的最高工资。

在第二行打印从 1 到 n 的 n 个数字的空格分隔排列 — 序列 v1, v2, ..., vn 中的车站数量。如果有多个答案,请打印其中任何一个。

示例

输入 #1

6 11
1 2 10
1 6 8
2 3 4
2 5 2
2 6 3
3 4 5
3 5 4
3 6 2
4 5 7
4 6 2
5 6 3

输出 #1

77
6 2 1 5 3 4