#include <iostream>
#include <algorithm>
#include <vector>

using std::vector;
typedef vector<vector<int> > Matrix;

const int INF = 1e9;

Matrix read_data() {
    int vertex_count, edge_count;
    std::cin >> vertex_count >> edge_count;
    Matrix graph(vertex_count, vector<int>(vertex_count, INF));
    for (int i = 0; i < edge_count; ++i) {
        int from, to, weight;
        std::cin >> from >> to >> weight;
        --from, --to;
        graph[from][to] = graph[to][from] = weight;
    }
    return graph;
}

std::pair<int, vector<int> > optimal_path_(const Matrix& graph) {
    // This solution tries all the possible sequences of stops.
    // It is too slow to pass the problem.
    // Implement a more efficient algorithm here.
    size_t n = graph.size();
    vector<int> p(n);
    for (size_t i = 0; i < n; ++i)
        p[i] = i;

    vector<int> best_path;
    int best_ans = INF;

    do {
        int cur_sum = 0;
        bool ok = true;
        for (size_t i = 1; i < n && ok; ++i)
            if (graph[p[i - 1]][p[i]] == INF)
                ok = false;
            else
                cur_sum += graph[p[i - 1]][p[i]];
        if (graph[p.back()][p[0]] == INF)
            ok = false;
        else
            cur_sum += graph[p.back()][p[0]];

        if (!ok)
            continue;
        if (cur_sum < best_ans) {
            best_ans = cur_sum;
            best_path = p;
        }
    } while (std::next_permutation(p.begin(), p.end()));

    if (best_ans == INF)
        best_ans = -1;
    for (size_t i = 0; i < best_path.size(); ++i)
        ++best_path[i];
    return std::make_pair(best_ans, best_path);
}

struct Memory {
    int w; int c; int r;
};

std::pair<int, vector<int> > optimal_path(const Matrix& graph) {

    int n = graph.size();   // edges
    int m = (1 << n);       // max combinations
    vector<vector<Memory>> cost(m, vector<Memory>(n, {INF, 0, 0}));
    cost[0][0] = {0, -1, -1};

    // C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i.
    // If size of S is 2, then S must be {1, i},
    //    C(S, i) = dist(1, i)
    for (int i = 1; i < n; i++) {
        int sid = (1 << i) + 1;
        int v = graph[0][i];
        if (v != INF) {
            cost[sid][i] = {v, 0, 0};
            // std::cout << "   set : ["<< sid << "][" << i << "] = " << cost[sid][i].w << std::endl;
        }
    }

    // Else if size of S is greater than 2.
    //    C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.
    // Note that 1 must be present in every subset S, so 1 less bit:
    m = (1 << (n - 1));
    for (int s = 2; s <= n; s++) {
        // std::cout << " size : " << s << std::endl;
        // loop from 0 ..m, with n=5, s=2 => 110, 101, 011
        for (int b = 0; b < m; b++) {
            int nb = 0;
            int v = b;
            while(v) {
                nb += (v & 1);  // check last bit
                v >>= 1;        // shift
            }
            if (nb != s) {
                continue;
            }
            // shift them and add 1 -> 1100, 1010, 0110
            int bits = (b << 1);
            // std::cout << "   bits : " << bits << std::endl;
            for (int i = 1; i < n; i++) { // not 0 it's our start
                if (bits & (1 << i)) {
                    for (int j = 0; j < n; j++) {
                        if (j != i && (bits & (1 << j))) {  // do not stay on the same vertex
                            int k = bits + 1;
                            int nk = (bits ^ (1 << i)) + 1;
                            // std::cout << "       try : " << nk << "->" << j << "->" << i <<std::endl;
                            int c = cost[nk][j].w + graph[j][i];
                            if (c < cost[k][i].w) {
                                cost[k][i] = {c, nk, j};
                                // std::cout << "   set : ["<< k << "][" << i << "] = " << c << std::endl;
                            }
                        }
                    }
                }
            }
        }
    }
    // std::cout << std::endl;
    // for (auto &row : cost) {
    //     for(auto &m : row) {
    //         std::cout << "   " << (m.w == INF ? 0 : m.w) << " (" << m.c << ";" << m.r << ") ";
    //     }
    //     std::cout << std::endl;
    // }
    // std::cout << std::endl;

    int best = INF;
    vector<int> path;

    auto &last_row = cost[(1 << n) - 1];
    Memory& last_m = cost[0][0];
    int j;
    for (int i = 0; i < cost[0].size(); i++) {
        auto &cell = last_row[i];
        int c = cell.w + graph[i][0];
        if (c < best) {
            j = i;
            best = c;
            last_m = cell;
        }
    }
    if (best == INF) {
        best = -1;
    } else {
        path.push_back(j + 1);
        while(last_m.r > 0) {
            // std::cout << last_m.w << " " << last_m.c << " " << last_m.r << std::endl;
            path.push_back(last_m.r + 1);
            last_m = cost[last_m.c][last_m.r];
        }
        path.push_back(1);
    }
    std::reverse(std::begin(path), std::end(path));

    return std::make_pair(best, path);
}

void print_answer(const std::pair<int, vector<int> >& answer) {
    std::cout << answer.first << "\n";
    if (answer.first == -1)
        return;
    const vector<int>& path = answer.second;
    for (size_t i = 0; i < path.size(); ++i)
        std::cout << path[i] << " ";
    std::cout << "\n";
}

int main() {
    print_answer(optimal_path(read_data()));
    return 0;
}