#include <fstream>
#include <vector>
#define INF 1000000000

using namespace std;

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

vector <int> l[20];

int n,m,x,y,d[20][(1<<19)],Min,i,j,k,cost[20][20],c,nod;

int minim (int a, int b) {
    if (a<b)
        return a;
    return b;
}

int main () {

    fin>>n>>m;

    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        l[x].push_back(y);
        cost[x][y]=c;
    }


    for (i=0;i<n;i++)
        for (j=0;j<=(1<<n)-1;j++)
            d[i][j]=INF;

    d[0][1]=0;

    for (j=1;j<(1<<n)-1;j++) {
        for (i=0;i<n;i++) {
            if (d[i][j]!=INF) {
                for (k=0;k<l[i].size();k++) {
                    nod=l[i][k];
                    if (((1<<nod)&j)==0)
                        d[nod][(1<<nod)|j]=minim(d[nod][(1<<nod)|j],d[i][j]+cost[i][nod]);
                }
            }
        }
    }
    Min=INF;
    for (i=1;i<n;i++)
        if (cost[i][0]!=0 && d[i][(1<<n)-1]+cost[i][0]<Min)
            Min=d[i][(1<<n)-1]+cost[i][0];
    if (Min==INF) {
        fout<<"Nu exista solutie\n";
        return 0;
    }

    fout<<Min<<"\n";

    return 0;
}