#include <bits/stdc++.h>
#define Nmax 18
#define INF 17000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m;
int a[Nmax][Nmax];
int pd[Nmax][1<<Nmax];
int main()
{
    int i,j,k,best=INF;
    f>>n>>m;
    while(m--)
    {
        f>>i>>j>>k;
        a[i][j]=k;
    }
    memset(pd,INF,sizeof(pd));
    int bit;
    pd[0][1]=1;
    for(bit=1;bit<(1<<n);bit++)
        for(i=0;i<n;i++)
        if(bit&(1<<i))
        {
            for(j=0;j<n;j++)
                if(a[i][j] and !(bit&(1<<j)))
                    if(a[i][j]+pd[i][bit]<pd[j][bit|(1<<j)])
                        pd[j][bit|(1<<j)]=a[i][j]+pd[i][bit];
        }
    int finish=(1<<n)-1;
    for(i=1;i<n;i++)
        if(a[i][0])
            best=min(best,a[i][0]+pd[i][finish]);
    if(best==INF) g<<"Nu exista solutie";
    else g<<best-1;

    return 0;
}