#include <fstream>
using namespace std;

const int DMAX = 100;

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

int n, m;
int ad[DMAX][DMAX];

int lgMin = 1e9;
int trMin[DMAX];

int lg;
int tr[DMAX];
bool vis[DMAX];

void bkt(int pos) {
    if (lg >= lgMin)
        return;

    if (pos == n + 1) {
        if (!ad[tr[n]][1])
            return;
        lg += ad[tr[n]][1];
        if (lg < lgMin) {
            lgMin = lg;
            for (int i = 1; i <= n; i++)
                trMin[i] = tr[i];
        }
        lg -= ad[tr[n]][1];
        return;
    }

    for (int i = 2; i <= n; i++)
        if (!vis[i] && ad[tr[pos - 1]][i]) {
            vis[tr[pos] = i] = true;
            lg += ad[tr[pos - 1]][i];
            bkt(pos + 1);
            vis[i] = false;
            lg -= ad[tr[pos - 1]][i];
        }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, z; fin >> x >> y >> z;
        ad[x][y] = ad[y][x] = z;
    }

    vis[tr[1] = 1] = true;
    bkt(2);

    fout << lgMin << '\n';
    for (int i = 1; i <= n; i++)
        fout << trMin[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}