#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <chrono>
#include <cmath>
using namespace std;

#define LIMIT 4.9

class Timer {
	chrono::high_resolution_clock::time_point start, end;
	double limit;

public:
	Timer() {
		start = chrono::high_resolution_clock::now();
	}
	Timer(double l) {
		start = chrono::high_resolution_clock::now();
		limit = l;
	}

	double getTime() {
		end = chrono::high_resolution_clock::now();
		return chrono::duration<double>(end - start).count();
	}

	bool Over() {
		if (getTime() > limit) {
			return true;
		}
		return false;
	}

	void setLimit(double l) {
		limit = l;
	}
	void setStart() { start = chrono::high_resolution_clock::now(); }
};

class Xor128 {
	unsigned static int x, y, z, w;
public:
	Xor128() {
		x = 31103110, y = 123456789, z = 521288629, w = 88675123;
	}

	unsigned int rand()
	{
		unsigned int t;
		t = (x ^ (x << 11)); x = y; y = z; z = w;
		return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
	}
};
unsigned int Xor128::x, Xor128::y, Xor128::z, Xor128::w;


int N, M;
int Score[50][50];

int nowScore(vector<int>&items) {
	int score = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			score += Score[items[i]][items[j]];
		}
	}

	return score;
}

int main()
{
	int maxItem=0, minItem = 10000;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
		Score[a][b] = c;
		maxItem = max(maxItem, c);
		minItem = min(minItem, c);
	}

	vector<int>items(N);
	for (int i = 0; i < N; i++) {
		items[i] = i;
	}

	int nowscore = nowScore(items);

	int maxscore = nowscore;
	vector<int>ans(items);

	Xor128 xor128;
	Timer tmr(LIMIT);
	while (!tmr.Over()) {
		int p1, p2;
		p1 = xor128.rand() % N;
		p2 = xor128.rand() % N;

		swap(items[p1], items[p2]);
		int tmpscore = nowScore(items);

		double starttemp = (maxItem-minItem+1)*4.;
		double endtemp = (maxItem - minItem + 1)*4./100.;
		double t = tmr.getTime();
		double temp = starttemp - (starttemp - endtemp) * t / LIMIT;

		if (tmpscore > nowscore) {
			nowscore = tmpscore;

			if (nowscore > maxscore) {
				maxscore = nowscore;
				ans = items;
			}
		}
		else if (exp((tmpscore - maxscore) / temp) > (double)xor128.rand() / UINT32_MAX) {
			nowscore = tmpscore;
		}
		else {
			swap(items[p1], items[p2]);
		}
	}

	cout << maxscore << endl;
	for (int i = 0; i < N; i++) {
		if (i)cout << " ";
		cout << ans[i];
	}
	cout << endl;

	cout << "多分これが一番良いと思います()" << endl;

    return 0;
}