#include <bits/stdc++.h>

using namespace std;

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

const int inf=1e9;
const int nmax=1<<18;

int n, m, v[20][20], dp[20][nmax];

void hamilton ()
{
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<nmax; j++)
            dp[i][j]=inf;
    }
    dp[0][1]=0;
    for (int k=1; k<(1<<n); k++)
    {
        for (int i=0; i<n; i++)
        {
            if (k&(1<<i))
            {
                for (int j=0; j<n; j++)
                {
                    if (!(k&(1<<j)) && v[i][j])
                        dp[j][k^(1<<j)]=min(dp[j][k^(1<<j)],dp[i][k]+v[i][j]);
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        v[x][y]=c;
    }
    hamilton();
    int rez=inf;
    for (int i=0; i<n; i++)
    {
        if (v[i][0])
            rez=min(rez,dp[i][(1<<n)-1]+v[i][0]);
    }
    if (rez==inf)
        fout << "Nu exista solutie";
    else
        fout << rez;
    return 0;
}