#include<fstream>
using namespace std;
int x[50],viz[50],smin,a[50][50],n,m, infinit=1000000000,i,j,u,v,c;

void bk(int k, int s)
{
    int i,ok,co,cn=infinit;
    if (k==n+1)
    {
        smin=s;
    }
    else
    {
        for (i=1;i<=n;i++)
        {
            if (viz[i]==0)
            {
                x[k]=i;
                ok=1;
                co=a[x[k-1]][i];
                if (k==n)
                {
                    cn=a[x[n]][x[1]];
                }
                if (s+co>=smin)
                {
                    ok=0;
                }
                if (k==n && cn==infinit)
                {
                    ok=0;
                }
                if (k==n && s+co+cn>=smin)
                {
                    ok=0;
                }
                if (ok==1)
                {
                    viz[i]=1;
                    if (k<n)bk(k+1,s+co);
                    else bk(k+1,s+co+cn);
                    viz[i]=0;
                }
            }
        }
    }
}

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin>>n>>m;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            a[i][j]=infinit;
        }
        a[i][i]=0;
    }
    for (i=1;i<=m;i++)
    {
        fin>>u>>v>>c;
        a[u+1][v+1]=c;
    }
    smin=infinit;
    x[1]=1;
    viz[1]=1;
    bk(2,0);
    if (smin<infinit)fout<<smin;
    else fout<<"Nu exista solutie";
    fin.close();
    fout.close();
    return 0;
}