#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<25;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;
#define N 64
#define M 1000
#define L 1000
int n, m;
int g[N][N], r[N], l[N];

int calc(vector<int> &a){
	int s = 0;
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			s += g[a[i]][a[j]];
		}
	}
	return s;
}

int opt(vector<int> &a){
	int res = calc(a);
	for(int i = 0; i < L; i++){
		int b = rand()%n, c = rand()%n;
		swap(a[b], a[c]);
		int r = calc(a);
		if(r<res){
			swap(a[b], a[c]);
			continue;
		}
		res = r;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n-1; j++){
			if(g[a[j]][a[j+1]]<g[a[j+1]][a[j]]) swap(a[j], a[j+1]);
		}
	}
	return res;
}

int main(){
	srand(time(NULL));
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		g[a][b] = c;
		r[b] += c;
		l[a] += c;
	}
	vector<int> res[M];
	vector<P> xx[2];
	for(int i = 0; i < n; i++){
		xx[0].push_back(P(r[i], i));
		xx[1].push_back(P(l[i], i));
	}
	sort(xx[0].begin(), xx[0].end());
	sort(xx[1].begin(), xx[1].end());
	for(int i = 0; i < n; i++){
		res[0].push_back(xx[0][i].second);
		res[1].push_back(xx[1][n-i-1].second);
		res[2].push_back(i);
	}
	for(int i = 3; i < M; i++) res[i] = res[2];
	for(int i = 2; i < M; i++)
		random_shuffle(res[i].begin(), res[i].end());
	/*
	for(int i = 0; i < M; i++){
		for(int j = 0; j < n; j++){
			cout<<res[i][j]<<" ";
		}
		cout<<endl;
	}
	*/
	int sc[M];
	for(int i = 0; i < M; i++) sc[i] = opt(res[i]);
	int mxp = 0;
	for(int i = 1; i < M; i++){
		if(sc[mxp]<sc[i]) mxp = i;
	}
	printf("%d\n", sc[mxp]);
	for(int i = 0; i < n; i++) printf("%d ", res[mxp][i]);
	return 0;
}