#include <bits/stdc++.h>
#define N 19
using namespace std;

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

int n,m,bitmax;
int a[N][N];
int dp[ (1<<N) ][N];

int main()
{
    fin >> n >> m;
    bitmax=( 1<<n )-1;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        a[x][y]=c;
    }
    fin.close();
    for(int i=0;i<=bitmax;i++)
        for(int j=0;j<n;j++)
            dp[i][j]=-1;
    ///
    dp[1][0]=0;
/// numai nr impare pt a il fixa pe 0   /// sarim pasul unu pt ca il are DOAR pe 0
    for(int bitmask=3;bitmask<=bitmax;bitmask+=2)
        for(int i=0;i<n;i++)
            if( bitmask&(1<<i) )
            {
                int bitmask2=bitmask-(1<<i);
                for(int j=0;j<n;j++)
                    if( dp[bitmask2][j]!=-1 and bitmask2&(1<<j) and a[j][i])
                        if( dp[bitmask][i]==-1 or dp[bitmask][i]>dp[bitmask2][j]+a[j][i] )
                            dp[bitmask][i] = dp[bitmask2][j]+a[j][i];
            }
    int sol=-1;
    for(int i=1;i<n;i++)
        if( (sol<0 and dp[bitmax][i] and a[i][0] ) or sol>dp[bitmax][i]+a[i][0] )
            sol=dp[bitmax][i] + a[i][0];
    if (sol == -1)fout << "Nu exista solutie\n";
    else fout << sol << "\n";
    fout.close();
    return 0;
}