#include <bits/stdc++.h>
#define Nmax 18
#define INF 17000000
#define DIM 700000
using namespace std;
class Ifstream
{
private:
    FILE *f;
    char *buffer;
    int cursor;
    char read_ch()
    {
        if(++cursor==DIM)
        {
            cursor=0;
            fread(buffer,1,DIM,f);
        }
        return buffer[cursor];
    }
public:
    Ifstream (const char *file_name)
    {
        f=fopen(file_name,"r");
        cursor=0;
        buffer=new char[DIM]();
    }
    Ifstream &operator >> (int &n)
    {
        char c;
        n=0;
        while(!isdigit(c=read_ch()));
        n=c-'0';
        while(isdigit(c=read_ch()))
            n=n*10+c-'0';
        return *this;
    }
};
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 finish=(1<<n)-1;
    int bit;
    pd[0][1]=1;
    for(bit=1;bit<=finish;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];
        }
    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;
}