#include <fstream>
#include <iostream>
#include <vector>
#include <iterator>
#include <limits>
#include <bitset>
#include <algorithm>
#include <cstdlib>
#include <cstdio>

#define MAXN 18
#define BIT(index) (1<<(index))
#define FULL_PATH_MASK(n) ((~(0xffffffff << (n))))

using namespace std;

typedef unsigned int uint32;

struct Edge
{
    Edge() :
        vertexID(0),
        cost(0)
    {}

    Edge(uint32 vID, int c) :
        vertexID(vID),
        cost(c)
    {}

    uint32 vertexID;
    int cost;
};

typedef vector<vector<Edge> > Graph;

Graph graph;

int costMatrix[1<<MAXN][MAXN];

int main()
{
    uint32 n, m;
    vector<uint32> vPath;
    fstream fin("hamilton.in", fstream::in);
    fstream fout("hamilton.out", fstream::out);
    
    fin >> n >> m;
    //cout << n << endl;
    
    graph.resize(n);
    
    for (int i=0; i<m; ++i)
    {
        uint32 x, y;
        int cost;

        fin >> x >> y >> cost;
        graph[y].push_back(Edge(x, cost));
    }

    /*for (auto& var : graph)
    {
        static int i = 0;
        cout << i++ << " <-- ";
        
        for (auto& edge : var)
        {
            cout << "(" << (int)edge.vertexID << " " << edge.cost << ") "; 
        }
        cout << endl;
    }*/
    
    for (uint32 possiblePath=0; possiblePath<(1<<n); ++possiblePath)
    {
        for (uint32 dest=0; dest<n; ++dest)
        {
            costMatrix[possiblePath][dest] = numeric_limits<int>::max()/2;
        }
    }

    costMatrix[1][0] = 0;
    
    for (uint32 possiblePath=1; possiblePath<(1<<n); ++possiblePath)
    {
        if ((possiblePath & 1) == 0) continue;

        for (uint32 dest=1; dest<n; ++dest)
        {
            if ((possiblePath & BIT(dest)) == 0) continue;

            for (int source=0; source<graph[dest].size(); ++source)
            {
                if ((possiblePath & BIT(graph[dest][source].vertexID)) == 0) continue;
                
                if ((possiblePath xor BIT(dest)) > 1 && graph[dest][source].vertexID == 0) continue;
                
                costMatrix[possiblePath][dest] =
                    min(costMatrix[possiblePath][dest],
                        graph[dest][source].cost + costMatrix[possiblePath xor BIT(dest)][graph[dest][source].vertexID]);
                
                /*cout << dest << " " << graph[dest][source].vertexID << " "
                     << std::bitset<19>(possiblePath) << " "
                     << possiblePath << " "
                     << costMatrix[possiblePath][dest] << endl;
                getchar();*/
                //cout << graph[dest][source].cost + costMatrix[possiblePath xor BIT(dest)][graph[dest][source].vertexID] << endl;
            }
        }
    }
    
    /*for (uint32 i=0; i<n; ++i)
    {
        cout << costMatrix[FULL_PATH_MASK(n)][i] << " ";
    }
    cout << endl;*/
    
    int startVertex = -1;
    int minCost = numeric_limits<int>::max()/2;
    for (int i=0; i<graph[0].size(); ++i)
    {
        const int pathCost = costMatrix[FULL_PATH_MASK(n)][graph[0][i].vertexID];
        if (minCost > graph[0][i].cost + pathCost)
        {
            minCost = graph[0][i].cost + pathCost;
            startVertex = graph[0][i].vertexID;
        }
    }

    if (minCost < numeric_limits<int>::max()/2)
    {
        fout << minCost << "\n";
        
        int path = FULL_PATH_MASK(n);
        do
        {
            vPath.push_back(startVertex);
            path ^= (1<<startVertex);
            
            minCost = numeric_limits<int>::max()/2;
            for (int i=0; (1<<i)<(1<<n); ++i)
            {
                if (((1<<i) & path) && costMatrix[path][i] < minCost)
                {
                    startVertex = i;
                }
            }
        } while (path);

        ostream_iterator<uint32> outIt(fout, " ");
        copy(vPath.begin(), vPath.end(), outIt);
        fout << "\n";
    }
    else
    {
        fout << "Nu exista solutie\n";
    }

    return 0;
}