#include <bits/stdc++.h>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int nmax=18;
const int imax=0x3f3f3f3f;
int n,m;
int v[nmax+1][nmax+1];
int d[1<<nmax][nmax];

int main()
{
    f>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        v[a][b]=c;
    }
    int maskmax=1<<n;

    for(int mask=0;mask<maskmax;mask++)
    {
        for(int j=0;j<n;j++)
        {
            d[mask][j]=imax;
        }
    }
    d[1][0]=0;

    for(int mask=0;mask<maskmax;mask++)
    {
        for(int j=0;j<n;j++)
        {

            if(!(mask&(1<<j))) continue;

            int mask2=mask-(1<<j);

            for(int k=0;k<n;k++)
            {
                if(!(mask2&(1<<k))) continue;
                if(v[k][j]==0) continue;
                d[mask][j]=min(d[mask][j],d[mask2][k]+v[k][j]);
            }

        }

    }
    int ans=imax;
    for(int i=0;i<n;i++)
    {
        if(v[i][0]==0) continue;

        ans=min(ans,v[i][0]+d[(1<<n)-1][i]);
    }
    if(ans==imax) g<<"Nu exista solutie\n";
    else g<<ans;
    return 0;
}