#include <fstream>
#include <algorithm>
#define inf 0x3f3f3f3f

using namespace std;

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

int c[262150][22],a[22][22],n,m,s[20][48630],b[20],nr[20];



void read()
{
    int x,y,c;
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            a[i][j]=inf;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        a[x][y]=c;
    }
}

void memo(int k)
{
    int sm=0,num=0;
    for(int i=1;i<=k;i++)
    {
        sm=sm*2+b[i];
        num+=b[i];
    }
    s[num][++nr[num]]=sm;
}

void bak(int k)
{
    for(int i=0;i<=1;i++)
    {
        b[k]=i;
        if(k==n)
            memo(k);
        if(k<n)
            bak(k+1);
    }
}

void write()
{
    /*for(int i=0;i<=n;i++)
    {
        for(int j=1;j<=nr[i];j++)
            fout<<s[i][j]<<" ";
        fout<<"\n";
    }*/
    for(int i=0;i<=n;i++)
    {
        for(int j=1;j<=nr[i];j++)
            for(int k=0;k<n;k++)
                fout<<c[s[i][j]][k]<<" ";
        fout<<"\n";
    }
}

void dinamica()
{
    int elj=1,s1,eli=1,rez,k,stf=1;
    c[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=nr[i];j++)
        {
            c[s[i][j]][0]=inf;
        }
    stf=1;
    for(int j=1;j<n;j++)
    {
        c[stf][j]=a[0][j];
        stf=stf<<1;
    }
    for(int l = 2;l<=n;l++)
    {

        for(int q=1;q<=nr[l];q++)
        {
            k=s[l][q];
            elj=1;
            for(int j=1;j<n;j++)
            {
                if(k&elj)
                {
                    s1=k^elj;
                    eli=1;
                    c[k][j]=inf;
                    for(int i=1;i<n;i++)
                    {
                        if((s1&eli)&&(i!=j))
                            c[k][j]=min(c[k][j],c[s1][i]+a[i][j]);
                        eli=eli<<1;
                    }
                }
                elj=elj<<1;
            }
        }
    }
    k=s[n-1][1];
    rez=inf;
    for(int j=1;j<n;j++)
        rez=min(c[k][j]+a[j][0],rez);
    if(rez>=inf)
        fout<<"Nu exista solutie";
    else
        fout<<rez<<"\n";
}

int main()
{
    read();
    bak(2);
    dinamica();
    //write();
    return 0;
}