Problem: 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 v1 and v2, and within one hour he pumps a certain amount of water from v1 to v2. Next, on the i-th day Mike chooses a station vi + 1 that has been never selected before, and pumps a certain amount of water out of the station vi to station vi + 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 v1, v2, ..., vn so Mike will be able to earn the highest possible salary.

Input

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 ai, bi and ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 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.

Output

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 v1, v2, ..., vn. If there are multiple answers, print any of them.

Examples

Input

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


Output

77
6 2 1 5 3 4 

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.List;
import java.util.stream.Stream;
import java.io.Closeable;
import java.io.Writer;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            EPumpingStations solver = new EPumpingStations();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class EPumpingStations {
        Comparator<IntegerWeightUndirectedEdge> comp = Comparator.comparingInt(x -> -x.weight);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int m = in.ri();
            List<IntegerFlowEdge>[] flow = Graph.createGraph(n);
            for (int i = 0; i < m; i++) {
                int a = in.ri() - 1;
                int b = in.ri() - 1;
                int c = in.ri();
                IntegerFlow.addFlowEdge(flow, a, b, c);
                IntegerFlow.addFlowEdge(flow, b, a, c);
            }
            IntegerGomoryHuTree tree = new IntegerGomoryHuTree(flow, new IntegerISAP());
            List<IntegerWeightUndirectedEdge>[] g = tree.tree();


            DSU dsu = new DSU(n);
            dsu.init();
            IntegerWeightUndirectedEdge best = null;
            for (List<IntegerWeightUndirectedEdge> adj : g) {
                for (IntegerWeightUndirectedEdge e : adj) {
                    if (best == null || comp.compare(e, best) < 0) {
                        best = e;
                    }
                }
            }

            int root = best.to;
            LeftistTree<IntegerWeightUndirectedEdge> pq = asLeftistTree(g[root]);
            IntegerArrayList ans = new IntegerArrayList(n);
            ans.add(root);
            long sum = 0;
            while (!pq.isEmpty()) {
                IntegerWeightUndirectedEdge head = pq.peek();
                pq = LeftistTree.pop(pq, comp);
                if (dsu.find(head.to) == dsu.find(root)) {
                    continue;
                }
                dsu.merge(head.to, root);
                sum += head.weight;
                ans.add(head.to);
                pq = LeftistTree.merge(pq, asLeftistTree(g[head.to]), comp);
            }

            out.println(sum);
            for (int x : ans.toArray()) {
                out.append(x + 1).append(' ');
            }
        }

        LeftistTree<IntegerWeightUndirectedEdge> asLeftistTree(List<IntegerWeightUndirectedEdge> adj) {
            LeftistTree<IntegerWeightUndirectedEdge> ans = LeftistTree.NIL;
            for (IntegerWeightUndirectedEdge e : adj) {
                LeftistTree<IntegerWeightUndirectedEdge> newInstance = new LeftistTree<>(e);
                ans = LeftistTree.merge(ans, newInstance, comp);
            }
            return ans;
        }

    }

    static class SequenceUtils {
        public static boolean equal(int[] a, int al, int ar, int[] b, int bl, int br) {
            if ((ar - al) != (br - bl)) {
                return false;
            }
            for (int i = al, j = bl; i <= ar; i++, j++) {
                if (a[i] != b[j]) {
                    return false;
                }
            }
            return true;
        }

    }

    static class LeftistTree<K> {
        public static final LeftistTree NIL = new LeftistTree<>(null);
        LeftistTree<K> left = NIL;
        LeftistTree<K> right = NIL;
        int dist;
        K key;

        static {
            NIL.left = NIL;
            NIL.right = NIL;
            NIL.dist = -1;
        }

        public LeftistTree(K key) {
            this.key = key;
        }

        public static <K> LeftistTree<K> merge(LeftistTree<K> a, LeftistTree<K> b, Comparator<K> cmp) {
            if (a == NIL) {
                return b;
            } else if (b == NIL) {
                return a;
            }
            if (cmp.compare(a.key, b.key) > 0) {
                LeftistTree<K> tmp = a;
                a = b;
                b = tmp;
            }
            a.right = merge(a.right, b, cmp);
            if (a.left.dist < a.right.dist) {
                LeftistTree<K> tmp = a.left;
                a.left = a.right;
                a.right = tmp;
            }
            a.dist = a.right.dist + 1;
            return a;
        }

        public boolean isEmpty() {
            return this == NIL;
        }

        public K peek() {
            return key;
        }

        public static <K> LeftistTree<K> pop(LeftistTree<K> root, Comparator<K> cmp) {
            LeftistTree<K> ans = merge(root.left, root.right, cmp);
            root.left = root.right = NIL;
            return ans;
        }

        private void toStringDfs(StringBuilder builder) {
            if (this == NIL) {
                return;
            }
            builder.append(key).append(' ');
            left.toStringDfs(builder);
            right.toStringDfs(builder);
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            toStringDfs(builder);
            return builder.toString();
        }

    }

    static class Graph {
        public static List[] createGraph(int n) {
            return IntStream.range(0, n).mapToObj(i -> new ArrayList<>()).toArray(i -> new List[i]);
        }

    }

    static class DSU {
        protected int[] p;
        public int[] size;
        protected int n;

        public DSU(int n) {
            p = new int[n];
            size = new int[n];
        }

        public void init() {
            init(p.length);
        }

        public void init(int n) {
            this.n = n;
            for (int i = 0; i < n; i++) {
                p[i] = i;
                size[i] = 1;
            }
        }

        public final int find(int a) {
            if (p[a] == p[p[a]]) {
                return p[a];
            }
            find(p[a]);
            preAccess(a);
            return p[a] = p[p[a]];
        }

        protected void preAccess(int a) {

        }

        protected void preMerge(int a, int b) {
            size[a] += size[b];
        }

        public final void merge(int a, int b) {
            a = find(a);
            b = find(b);
            if (a == b) {
                return;
            }

            if (size[a] < size[b]) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            preMerge(a, b);
            p[b] = a;
        }

        public String toString() {
            return Arrays.toString(Arrays.copyOf(p, n));
        }

    }

    static interface IntegerStack {
        void addLast(int x);

        boolean isEmpty();

        void clear();

    }

    static class IntegerWeightUndirectedEdge extends IntegerWeightDirectedEdge {
        public IntegerWeightUndirectedEdge rev;

        public IntegerWeightUndirectedEdge(int to, int weight) {
            super(to, weight);
        }

    }

    static class IntegerDequeImpl implements IntegerDeque {
        private int[] data;
        private int bpos;
        private int epos;
        private static final int[] EMPTY = new int[0];
        private int n;

        public IntegerDequeImpl(int cap) {
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
            bpos = 0;
            epos = 0;
            n = cap;
        }

        private void expandSpace(int len) {
            while (n < len) {
                n = Math.max(n + 10, n * 2);
            }
            int[] newData = new int[n];
            if (bpos <= epos) {
                if (bpos < epos) {
                    System.arraycopy(data, bpos, newData, 0, epos - bpos);
                }
            } else {
                System.arraycopy(data, bpos, newData, 0, data.length - bpos);
                System.arraycopy(data, 0, newData, data.length - bpos, epos);
            }
            epos = size();
            bpos = 0;
            data = newData;
        }

        public IntegerIterator iterator() {
            return new IntegerIterator() {
                int index = bpos;


                public boolean hasNext() {
                    return index != epos;
                }


                public int next() {
                    int ans = data[index];
                    index = IntegerDequeImpl.this.next(index);
                    return ans;
                }
            };
        }

        public int removeFirst() {
            int ans = data[bpos];
            bpos = next(bpos);
            return ans;
        }

        public void addLast(int x) {
            ensureMore();
            data[epos] = x;
            epos = next(epos);
        }

        public void clear() {
            bpos = epos = 0;
        }

        private int next(int x) {
            return x + 1 >= n ? 0 : x + 1;
        }

        private void ensureMore() {
            if (next(epos) == bpos) {
                expandSpace(n + 1);
            }
        }

        public int size() {
            int ans = epos - bpos;
            if (ans < 0) {
                ans += data.length;
            }
            return ans;
        }

        public boolean isEmpty() {
            return bpos == epos;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (IntegerIterator iterator = iterator(); iterator.hasNext(); ) {
                builder.append(iterator.next()).append(' ');
            }
            return builder.toString();
        }

    }

    static class IntegerFlowEdge<T extends IntegerFlowEdge<T>> extends DirectedEdge {
        public int flow;
        public boolean real;
        public T rev;

        public IntegerFlowEdge(int to, int flow, boolean real) {
            super(to);
            this.flow = flow;
            this.real = real;
        }

        public String toString() {
            return rev.to + "-[" + flow + "/" + (flow + rev.flow) + "]->" + to;
        }

    }

    static interface IntegerDeque extends IntegerStack {
        int removeFirst();

    }

    static class IntegerISAP implements IntegerMaximumFlow {
        private List<IntegerFlowEdge>[] net;
        private int s;
        private int t;
        private int[] dists;
        private int[] cnts;
        private int n;
        private boolean exit;
        private IntegerDeque deque;

        public IntegerISAP() {
        }

        public void ensure(int vertexNum) {
            if (dists != null && dists.length >= vertexNum) {
                return;
            }
            dists = new int[vertexNum];
            cnts = new int[vertexNum + 2];
            deque = new IntegerDequeImpl(n);
        }

        private int send(int root, int flow) {
            if (root == t) {
                return flow;
            }
            int snapshot = flow;
            for (IntegerFlowEdge e : net[root]) {
                int remain;
                if (dists[e.to] + 1 != dists[root] || (remain = e.rev.flow) == 0) {
                    continue;
                }
                int sent = send(e.to, Math.min(flow, remain));
                flow -= sent;
                IntegerFlow.send(e, sent);
                if (flow == 0 || exit) {
                    break;
                }
            }
            if (flow == snapshot) {
                cnts[dists[root]]--;
                dists[root]++;
                cnts[dists[root]]++;
                if (cnts[dists[root] - 1] == 0) {
                    exit = true;
                }
            }
            return snapshot - flow;
        }

        public int apply(List<IntegerFlowEdge>[] g, int s, int t, int send) {
            ensure(g.length);
            this.net = g;
            this.s = s;
            this.t = t;
            this.exit = false;
            n = g.length;
            IntegerFlow.bfsForFlow(g, t, dists, n + 1, deque);
            Arrays.fill(cnts, 0, n + 2, 0);
            for (int d : dists) {
                cnts[d]++;
            }
            int flow = 0;
            while (flow < send && !exit && dists[s] < n) {
                flow += send(s, send - flow);
            }
            return flow;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class IntegerArrayList implements Cloneable {
        private int size;
        private int cap;
        private int[] data;
        private static final int[] EMPTY = new int[0];

        public IntegerArrayList(int cap) {
            this.cap = cap;
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
        }

        public IntegerArrayList(int[] data) {
            this(0);
            addAll(data);
        }

        public IntegerArrayList(IntegerArrayList list) {
            this.size = list.size;
            this.cap = list.cap;
            this.data = Arrays.copyOf(list.data, size);
        }

        public IntegerArrayList() {
            this(0);
        }

        public void ensureSpace(int req) {
            if (req > cap) {
                while (cap < req) {
                    cap = Math.max(cap + 10, 2 * cap);
                }
                data = Arrays.copyOf(data, cap);
            }
        }

        private void checkRange(int i) {
            if (i < 0 || i >= size) {
                throw new ArrayIndexOutOfBoundsException("Access [" + i + "]");
            }
        }

        public int get(int i) {
            checkRange(i);
            return data[i];
        }

        public void add(int x) {
            ensureSpace(size + 1);
            data[size++] = x;
        }

        public void addAll(int[] x) {
            addAll(x, 0, x.length);
        }

        public void addAll(int[] x, int offset, int len) {
            ensureSpace(size + len);
            System.arraycopy(x, offset, data, size, len);
            size += len;
        }

        public void addAll(IntegerArrayList list) {
            addAll(list.data, 0, list.size);
        }

        public int size() {
            return size;
        }

        public int[] toArray() {
            return Arrays.copyOf(data, size);
        }

        public String toString() {
            return Arrays.toString(toArray());
        }

        public boolean equals(Object obj) {
            if (!(obj instanceof IntegerArrayList)) {
                return false;
            }
            IntegerArrayList other = (IntegerArrayList) obj;
            return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1);
        }

        public int hashCode() {
            int h = 1;
            for (int i = 0; i < size; i++) {
                h = h * 31 + Integer.hashCode(data[i]);
            }
            return h;
        }

        public IntegerArrayList clone() {
            IntegerArrayList ans = new IntegerArrayList();
            ans.addAll(this);
            return ans;
        }

    }

    static interface IntegerIterator {
        boolean hasNext();

        int next();

    }

    static class IntegerGomoryHuTree {
        private List<IntegerWeightUndirectedEdge>[] ug;
        private int[][] minCuts;
        private static final int INF = Integer.MAX_VALUE / 4;

        public IntegerGomoryHuTree(List<IntegerFlowEdge>[] g, IntegerMaximumFlow mf) {
            int n = g.length;
            ug = IntegerWeightGraph.createUndirectedGraph(n);
            minCuts = new int[n][n];
            IntegerArrayList list = new IntegerArrayList(n);
            for (int i = 0; i < n; i++) {
                list.add(i);
            }
            dac(list, g, mf, new boolean[n]);
            for (int i = 0; i < n; i++) {
                dfs(i, -1, INF, minCuts[i]);
            }
        }

        public List<IntegerWeightUndirectedEdge>[] tree() {
            return ug;
        }

        private void addEdge(int s, int t, int f) {
            //System.err.printf("(%d,%d)=%d\n", s, t, f);
            IntegerWeightGraph.addUndirectedEdge(ug, s, t, f);
        }

        private void dfs(int root, int p, int w, int[] minCuts) {
            minCuts[root] = w;
            for (IntegerWeightUndirectedEdge e : ug[root]) {
                if (e.to == p) {
                    continue;
                }
                dfs(e.to, root, Math.min(w, e.weight), minCuts);
            }
        }

        private void dac(IntegerArrayList set, List<IntegerFlowEdge>[] g, IntegerMaximumFlow mf, boolean[] visited) {
            if (set.size() <= 1) {
                return;
            }
            //rebuild the flow
            IntegerFlow.rewind(g);
            int s = set.get(0);
            int t = set.get(1);
            int f = mf.apply(g, s, t, INF);
            addEdge(s, t, f);
            IntegerFlow.findSetST(g, s, visited);
            IntegerArrayList l1 = new IntegerArrayList(set.size());
            IntegerArrayList l2 = new IntegerArrayList(set.size());
            for (int i = set.size() - 1; i >= 0; i--) {
                int v = set.get(i);
                if (visited[v]) {
                    l1.add(v);
                } else {
                    l2.add(v);
                }
            }
            dac(l1, g, mf, visited);
            dac(l2, g, mf, visited);
        }

    }

    static class IntegerWeightGraph {
        public static void addUndirectedEdge(List<IntegerWeightUndirectedEdge>[] g, int s, int t, int w) {
            IntegerWeightUndirectedEdge toT = new IntegerWeightUndirectedEdge(t, w);
            IntegerWeightUndirectedEdge toS = new IntegerWeightUndirectedEdge(s, w);
            toS.rev = toT;
            toT.rev = toS;
            g[s].add(toT);
            g[t].add(toS);
        }

        public static List<IntegerWeightUndirectedEdge>[] createUndirectedGraph(int n) {
            List<IntegerWeightUndirectedEdge>[] ans = new List[n];
            for (int i = 0; i < n; i++) {
                ans[i] = new ArrayList<>();
            }
            return ans;
        }

    }

    static class IntegerWeightDirectedEdge extends DirectedEdge {
        public int weight;

        public IntegerWeightDirectedEdge(int to, int weight) {
            super(to);
            this.weight = weight;
        }

    }

    static interface IntegerMaximumFlow {
        int apply(List<IntegerFlowEdge>[] g, int s, int t, int send);

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static boolean equal(int a, int b) {
            return a == b;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class DirectedEdge {
        public int to;

        public DirectedEdge(int to) {
            this.to = to;
        }

        public String toString() {
            return "->" + to;
        }

    }

    static class IntegerFlow {
        public static void findSetST(List<IntegerFlowEdge>[] g, int s, boolean[] visited) {
            Arrays.fill(visited, false);
            dfs(g, visited, s);
        }

        private static void dfs(List<IntegerFlowEdge>[] g, boolean[] visited, int root) {
            if (visited[root]) {
                return;
            }
            visited[root] = true;
            for (IntegerFlowEdge e : g[root]) {
                if (!DigitUtils.equal(e.rev.flow, 0)) {
                    dfs(g, visited, e.to);
                }
            }
        }

        public static <T extends IntegerFlowEdge> void send(T edge, int flow) {
            edge.flow += flow;
            edge.rev.flow -= flow;
        }

        public static IntegerFlowEdge addFlowEdge(List[] g, int s, int t, int cap) {
            IntegerFlowEdge real = new IntegerFlowEdge(t, 0, true);
            IntegerFlowEdge virtual = new IntegerFlowEdge(s, cap, false);
            real.rev = virtual;
            virtual.rev = real;
            g[s].add(real);
            g[t].add(virtual);
            return real;
        }

        public static <T extends IntegerFlowEdge> void bfsForFlow(List<T>[] g, int s, int[] dist, int inf, IntegerDeque deque) {
            Arrays.fill(dist, 0, g.length, inf);
            dist[s] = 0;
            deque.clear();
            deque.addLast(s);
            while (!deque.isEmpty()) {
                int head = deque.removeFirst();
                for (T e : g[head]) {
                    if (!DigitUtils.equal(e.flow, 0) && dist[e.to] == inf) {
                        dist[e.to] = dist[head] + 1;
                        deque.addLast(e.to);
                    }
                }
            }
        }

        public static <T extends IntegerFlowEdge> void rewind(List<T>[] g) {
            for (int i = 0; i < g.length; i++) {
                for (T e : g[i]) {
                    if (e.real) {
                        e.rev.flow += e.flow;
                        e.flow = 0;
                    }
                }
            }
        }

    }
}