#include <fstream>
#include <vector>
#include <climits>
#define NMAX 20
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int N, M;
const long long INFLL = (1LL<<60);
long long cmin;
int ok;
int A[NMAX][NMAX];   // A[u][v] = cost sau -1/INF marker
int x[NMAX], best_sol[NMAX];

// citire: intrare 1-based -> convertim intern la 0-based
void citire() {
    fin >> N >> M;
    // init cu -1 (fara muchie)
    for (int i = 0; i < NMAX; ++i)
        for (int j = 0; j < NMAX; ++j)
            A[i][j] = -1;

    int u, v, cost;
    for (int k = 0; k < M; ++k) {
        fin >> u >> v >> cost;
        // convert 1-based -> 0-based

        if (u >= 0 && u < N && v >= 0 && v < N) {
            A[u][v] = cost;
        }
    }
}

// verifică permutarea curentă x[0..N-1]; actualizează cmin și best_sol
void prelucrare_sol() {
    // verifică existența arcelor pe ciclul x[0]->x[1]->...->x[N-1]->x[0]
    long long total = 0;
    for (int i = 1; i < N; ++i) {
        int cu = x[i-1], cv = x[i];
        if (A[cu][cv] == -1) return; // muchie lipsă -> nu e ciclu hamiltonian
        total += (long long)A[cu][cv];
        // mică optimizare: dacă total deja >= cmin, putem tăia (dar cmin poate fi INF la început)
        if (total >= cmin) return;
    }
    // ultima muchie
    if (A[x[N-1]][x[0]] == -1) return;
    total += (long long)A[x[N-1]][x[0]];

    if (total < cmin) {
        cmin = total;
        for (int i = 0; i < N; ++i) best_sol[i] = x[i];
        ok = 1;
    }
}

// Heap's algorithm (recursiv) pentru permutări — folosit ca backtracking
void BACK(int k) {
    if (k == 1) {
        prelucrare_sol();
        return;
    }
    for (int i = 0; i < k; ++i) {
        BACK(k - 1);
        if (k % 2 == 1) {
            // k impar: swap primul cu ultimul
            int tmp = x[0]; x[0] = x[k-1]; x[k-1] = tmp;
        } else {
            // k par: swap i cu ultimul
            int tmp = x[i]; x[i] = x[k-1]; x[k-1] = tmp;
        }
    }
}

int main() {
    citire();

    if (N > NMAX) {
        fout << "N este mai mare decat " << NMAX << "\n";
        return 0;
    }

    // initializare permutare 0..N-1 (intern 0-based)
    for (int i = 0; i < N; ++i) x[i] = i;

    cmin = INFLL;
    ok = 0;

    // Generăm toate permutările cu Heap
    BACK(N);

    if (ok) {
        fout << cmin << "\n";
        // Afisăm ciclul in forma 1-based (pentru a corespunde intrării 1-based)
        for (int i = 0; i < N; ++i) {
            fout << (best_sol[i] + 1);
            if (i + 1 < N) fout << " ";
        }
        fout << "\n";
    } else {
        fout << "Nu exista solutie\n";
    }

    return 0;
}