package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type Edge struct {
	to, cap, flow, rev int
}

var (
	adj     [][]Edge
	level   []int
	ptr     []int
	visited []bool
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func addEdge(from, to, cap int) {
	adj[from] = append(adj[from], Edge{to, cap, 0, len(adj[to])})
	adj[to] = append(adj[to], Edge{from, cap, 0, len(adj[from]) - 1})
}

func bfs(s, t int) bool {
	for i := range level {
		level[i] = -1
	}
	level[s] = 0
	q := []int{s}
	for len(q) > 0 {
		v := q[0]
		q = q[1:]
		for _, edge := range adj[v] {
			if edge.cap-edge.flow > 0 && level[edge.to] == -1 {
				level[edge.to] = level[v] + 1
				q = append(q, edge.to)
			}
		}
	}
	return level[t] != -1
}

func dfsDinic(v, t, pushed int) int {
	if pushed == 0 || v == t {
		return pushed
	}
	for ; ptr[v] < len(adj[v]); ptr[v]++ {
		edge := &adj[v][ptr[v]]
		tr := edge.to
		if level[v]+1 != level[tr] || edge.cap-edge.flow == 0 {
			continue
		}
		push := dfsDinic(tr, t, min(pushed, edge.cap-edge.flow))
		if push == 0 {
			continue
		}
		edge.flow += push
		adj[tr][edge.rev].flow -= push
		return push
	}
	return 0
}

func dinic(s, t int) int {
	flow := 0
	for bfs(s, t) {
		for i := range ptr {
			ptr[i] = 0
		}
		for {
			pushed := dfsDinic(s, t, 1000000000)
			if pushed == 0 {
				break
			}
			flow += pushed
		}
	}
	return flow
}

func dfsCut(v int) {
	visited[v] = true
	for _, edge := range adj[v] {
		if edge.cap-edge.flow > 0 && !visited[edge.to] {
			dfsCut(edge.to)
		}
	}
}

type TreeEdge struct {
	u, v, w int
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m int
	if _, err := fmt.Fscan(reader, &n, &m); err != nil {
		return
	}

	adj = make([][]Edge, n)
	level = make([]int, n)
	ptr = make([]int, n)
	visited = make([]bool, n)

	for i := 0; i < m; i++ {
		var u, v, w int
		fmt.Fscan(reader, &u, &v, &w)
		u--
		v--
		addEdge(u, v, w)
	}

	p := make([]int, n)
	var treeEdges []TreeEdge

	for i := 1; i < n; i++ {
		for u := 0; u < n; u++ {
			for j := range adj[u] {
				adj[u][j].flow = 0
			}
		}

		flow := dinic(i, p[i])
		treeEdges = append(treeEdges, TreeEdge{i, p[i], flow})

		for k := range visited {
			visited[k] = false
		}
		dfsCut(i)

		for j := i + 1; j < n; j++ {
			if p[j] == p[i] && visited[j] {
				p[j] = i
			}
		}
	}

	sort.Slice(treeEdges, func(i, j int) bool {
		return treeEdges[i].w > treeEdges[j].w
	})

	seq := make([][]int, n)
	parent := make([]int, n)
	for i := 0; i < n; i++ {
		seq[i] = []int{i}
		parent[i] = i
	}

	var find func(int) int
	find = func(i int) int {
		if parent[i] == i {
			return i
		}
		parent[i] = find(parent[i])
		return parent[i]
	}

	ans := 0
	for _, e := range treeEdges {
		ans += e.w
		u := find(e.u)
		v := find(e.v)
		if u != v {
			parent[v] = u
			seq[u] = append(seq[u], seq[v]...)
		}
	}

	fmt.Println(ans)
	root := find(0)
	for i := 0; i < n; i++ {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(seq[root][i] + 1)
	}
	fmt.Println()
}