#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
const int N = 1e5 + 5, INF = 1e9;

int dp[20][(1ll << 19)], graf[20][20];


int main()
{
    ios_base::sync_with_stdio(0);
    int n,m,i,j,k,t,q,nr,minim,maxim,suma;
    fin>>n>>m;
	for (i = 1; i <= m; i++)
    {
		fin>>j>>k>>t;
		graf[j][k] = t;
	}


	for ( i = 0; i < n; i++)
    {
		for (int bitmask = 0; bitmask < (1ll << n); bitmask++)
        {
			dp[i][bitmask] = INF;
		}
	}
    dp[0][1]=0;
    for(int bitmask = 1; bitmask<(1ll<<n); bitmask++)
    {
        for(i=0;i<n;i++) // ultimul nod pe care il adaugam la un dp anterior pentru a obtine dp[masca]
        {
            if(bitmask & (1ll<<i)) // daca nodul i apartine drumului specificat de masca
            {
                for(j=0;j<n;j++) // ultimul dp de la care puteam ajunge
                {
                    if(i!=j && graf[j][i] && (bitmask & (1ll<<j)))
                    {
                        dp[i][bitmask] = min(dp[i][bitmask] , dp[j][bitmask ^ (1ll<<i)] + graf[j][i]);
                    }
                }
            }
        }
    }

    minim=INF;
    for(i=1;i<n;i++)
    {
        if(graf[i][0])
            minim=min(minim,dp[i][(1ll<<n)-1]+graf[i][0]);
    }

    if(minim!=INF)
        fout<<minim<<'\n';
    else
        fout<<"Nu exista solutie\n";



    return 0;
}