疯狂科学家迈克已申请一份工作。他的任务是管理水泵站系统。
系统由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