CF343E.Pumping Stations

Mad scientist Mike has applied for a job. His task is to manage a system of water pumping stations.

The system consists of n pumping stations, which are numbered by integers from 1 to n. Some pairs of stations are connected by bidirectional pipes through which water can flow in either direction (but only in one at a time). For each pipe you know its bandwidth — the maximum number of liters of water that can flow through it in one hour. Each pumping station can pump incoming water from some stations to other stations through the pipes, provided that in one hour the total influx of water to the station is equal to the total outflux of water from the station.

It is Mike's responsibility to pump water between stations. From station a to station b through the pipes (possibly through other stations) within one hour one can transmit a certain number of liters of water according to the rules described above. During this time, water from other stations can not flow into station a, and can not flow out of the station b. However, any amount of water can flow out of station a or in station b. If a total of x litres of water flows out of the station a in an hour, then Mike gets x bollars more to his salary.

To get paid, Mike needs to work for n - 1 days, according to the contract. On the first day he selects two stations _v_1 and _v_2, and within one hour he pumps a certain amount of water from _v_1 to _v_2. Next, on the i-th day Mike chooses a station v__i + 1 that has been never selected before, and pumps a certain amount of water out of the station v__i to station v__i + 1 for one hour. The quantity of water he pumps on the i-th day does not depend on the amount of water pumped on the (i - 1)-th day.

Mike needs to earn as much bollars as he can for his projects. Help Mike find such a permutation of station numbers _v_1, _v_2, ..., v__n so Mike will be able to earn the highest possible salary.

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

该系统由 $n$ 个水泵站组成，编号为 $1$ 到 $n$ 的整数。某些水泵站对之间通过双向管道相连，水可在其中沿任一方向流动（但任意时刻只能单向流动）。每条管道都有其带宽——即一小时内可通过的最大水量（单位：升）。每个水泵站均可将来自某些站点的进水，经管道泵送至其他站点，前提是：在一小时内，流入该站的总水量必须等于从该站流出的总水量。

迈克负责在各站点之间泵送水。根据上述规则，一小时内可从站点 $a$ 经管道（可能途经其他站点）向站点 $b$ 传输一定量的水。在此期间，不允许其他站点的水流入站点 $a$，也不允许水从站点 $b$ 流出；但允许任意数量的水从站点 $a$ 流出，或流入站点 $b$。若一小时内从站点 $a$ 流出的总水量为 $x$ 升，则迈克的薪水将增加 $x$ 博拉尔（bollars）。

为获得报酬，迈克需按合同工作 $n-1$ 天。第一天，他选择两个站点 $v_1$ 和 $v_2$，并在一小时内从 $v_1$ 向 $v_2$ 泵送一定量的水；随后，在第 $i$ 天，他选择一个此前从未选过的站点 $v_{i+1}$，并在一小时内从站点 $v_i$ 向 $v_{i+1}$ 泵送一定量的水。第 $i$ 天泵送的水量与第 $i-1$ 天泵送的水量无关。

迈克希望为其科研项目赚取尽可能多的博拉尔。请帮助迈克找出一个站点编号的排列 $v_1, v_2, \dots, v_n$，使得他能获得最高的可能薪水。

The first line of the input contains two space-separated integers n and m (2 ≤ n ≤ 200, 1 ≤ m ≤ 1000) — the number of stations and pipes in the system, accordingly. The i-th of the next m lines contains three space-separated integers a__i, b__i and c__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 1 ≤ c__i ≤ 100) — the numbers of stations connected by the i-th pipe and the pipe's bandwidth, accordingly. It is guaranteed that any two stations are connected by at most one pipe and that there is a pipe path between any two stations.

输入的第一行包含两个以空格分隔的整数 $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$ 条管道所连接的两个车站编号以及该管道的带宽。保证任意两个车站之间至多只有一条管道相连，且任意两个车站之间均存在一条管道路径。

On the first line print a single integer — the maximum salary Mike can earn.

On the second line print a space-separated permutation of n numbers from 1 to n — the numbers of stations in the sequence _v_1, _v_2, ..., v__n. If there are multiple answers, print any of them.

第一行输出一个整数——Mike 能获得的最高薪水。

第二行输出一个由 $1$ 到 $n$ 的 $n$ 个数字组成的、以空格分隔的排列——即序列 $v_1, v_2, \dots, v_n$ 中各车站的编号。若存在多个答案，输出任意一个即可。