#include <iostream>
#include <fstream>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int MAX = 10000000;
int mat[20][20], x[20], s=0, mini=MAX, n;
//s este lungimea drumului, mini este s minim
void afis() //aici trec printr-o permutare intreaga, deci calculez s
{
    s=0;
    int ok=1, a, b;
    for(int i=1; i<=n; ++i)
    {
        a=x[i-1]-1;
        b=x[i]-1;
        if(mat[a][b]!=0)
            s=s+mat[a][b];
        else
            ok=0;
        cout<<x[i]<<" ";
    }
    a=x[1]-1;
    b=x[n]-1;
    if(mat[a][b]!=0)
        s=s+mat[a][b];
    else
        ok=0;
    if(ok==1)
        cout<<"    suma la final de drum "<<s<<'\n';
    else
        cout<<'\n';
    if(s<mini)
        mini=s;
}
bool ok(int k)
{
    for(int i=1; i<k; ++i)
    {
        if(x[i]==x[k])
            return false;
    }
    return true;
}
void bkt(int k)
{
    for(int i=1; i<=n; ++i)
    {
        x[k]=i;
        if(ok(k))
        {
            if(k==n)
                afis();
        else
            bkt(k+1);
        }
    }
}
int main()
{
    int m;
    in>>n>>m;
    for(int i=0; i<m; ++i)
    {
        int x,y,z;
        in>>x>>y>>z;
        if(mat[x][y]==0 || mat[x][y]>z)
            mat[x][y]=mat[y][x]=z;
    }
    bkt(1);
    out<<mini;
    cout<<'\n'<<'\n'<<"minimul este "<<mini;
    return 0;
}