#include <bits/stdc++.h>

#define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;

int item1[55], item2[55], score[55];
int mat[55][55];
int N, M;

// 乱数生成
unsigned int randxor() {
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned int t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

int getScore(const vector<int>& seq) {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            ret += mat[seq[i]][seq[j]];
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> item1[i] >> item2[i] >> score[i];
        mat[item1[i]][item2[i]] = score[i];
    }
    vector<int> currentSeq(N);
    for (int i = 0; i < N; i++) currentSeq[i] = i;
    vector<int> bestSeq = currentSeq;
    int bestScore = getScore(currentSeq);
    int currentScore = bestScore;
    auto start = std::chrono::system_clock::now();
    ll restTime = 0;
    int timeCnt = 0;
    while (1) {
        //for (int i = 0 ; i < N; i++) cout << currentSeq[i] << "  ";
        //cout << endl;
        if (timeCnt >= 100) {
            timeCnt = 0;
            auto now = std::chrono::system_clock::now();
            auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(now-start);
            restTime = duration.count();
            if (restTime >= 4800) break;
        }
        timeCnt++;
        int r = randxor() % N;
        int q = randxor() % N;
        bool FORCE_MOVE = randxor()%100000 < (4800-restTime);
        swap(currentSeq[r], currentSeq[q]);
        int nextScore = getScore(currentSeq);
        if (nextScore > currentScore || FORCE_MOVE) {
            currentScore = nextScore;
        } else {
            swap(currentSeq[r], currentSeq[q]);
        }
        if (bestScore < currentScore) {
            bestSeq = currentSeq;
            bestScore = currentScore;
        }
    }
    cout << bestScore << endl;
    for (int i = 0; i < N; i++) {
        cout << bestSeq[i] << endl;
    }
    return 0;
}