#include <fstream>
#include <vector>
#define nmax 18
#define inf 100000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
vector <int> a[nmax],b[nmax];
vector <int> ::iterator it1,it2;
int n,m;
int v[nmax+5][1<<(nmax)+5];


int main()
{
    int i,j,x,y,z;
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>x>>y>>z;
        a[x].push_back(y);b[x].push_back(z);
    }

    for (j=1;j<=(1<<(n));j++)
        for (i=0;i<n;i++)
                v[i][j]=inf;
    v[0][1]=0;

    for (j=1;j<(1<<n)-1;j++)
        for (i=0;i<n;i++)
            if (v[i][j]!=inf)
            {
                //suntem in starea i,j
                it1=a[i].begin();
                it2=b[i].begin();
                for (;it1!=a[i].end();it1++,it2++) {
                        x=*it1;
                        z=*it2;
                        if ((j&(1<<x))==0) {
                                y=j+(1<<x);
                                v[x][y]=min(v[x][y],v[i][j]+z);
                        }
                }
    }
    j=1<<n;
    for (i=1;i<=n;i++) {
        it1=a[i].begin();
        it2=b[i].begin();
        for (;it1!=a[i].end();it1++,it2++) {
                x=*it1;
                z=*it2;
                if (x==0)
                    v[0][j]=min(v[0][j],v[i][j-1]+z);
        }
    }
    if (v[0][j]==inf)
        g<<"Nu exista solutie";
    else
        g<<v[0][j];
    return 0;
}