#include <bits/stdc++.h>

using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
int dp[1<<18][18], n, m, x, y, c, h[18][18];
int main()
{
    fin >> n >> m;

    for(int i=1;i<=m;i++)
    {
        fin >> x >> y >> c;
        h[x][y]=c;

    }

    for(int i=1;i<n;i++)
        dp[0][i]=-1;

    for(int m=1;m<(1<<n);m++)
        for(int i=0;i<n;i++)
        {
            dp[m][i]=-1;
            if(m & (1<<i))
            {
                int aux=m^(1<<i);
                for(int j=0;j<n;j++)
                    if(h[j][i]>0 && dp[aux][j]!=-1)
                    {
                        if(dp[m][i]==-1)
                            dp[m][i]=dp[aux][j]+h[j][i];
                        else dp[m][i]=min(dp[m][i], dp[aux][j]+h[j][i]);
                    }
            }
        }
    if(dp[(1<<n)-1][0]==-1)
        fout << "Nu exista solutie";
    else fout << dp[(1<<n)-1][0];
    return 0;
}