#include <bits/stdc++.h>
#define VMax 262144
#define NMax 18
#define oo 1<<29
using namespace std;

vector<int> t[NMax+1];
int cost[NMax+1][NMax+1];
int dp[NMax+1][VMax+1];
int nr[VMax+1];
int N;

void Precalc()
{
    int i,x;
    for(i = 1; i <= 1<<N; ++i)
        for(x = i; x; x>>=1) nr[i] += x&1;
    for(i = 1; i < 1<<N; ++i) t[ nr[i] ].push_back(i);
}

int main(){
    FILE* fin = fopen("hamilton.in","r");
    FILE* fout = fopen("hamilton.out","w");

    int i,j,x,y,c,mask,M,res=oo;

    fscanf(fin,"%d %d",&N,&M);
    for(i = 1; i <= N; ++i)
        for(j = 1; j <= N; ++j) cost[i][j] = oo;
    for(i = 1; i <= M; ++i)
    {
        fscanf(fin,"%d %d %d",&x,&y,&c);
        cost[++x][++y] = c;
    }

    for(i = 1; i <= N; ++i)
        for(j = 1; j < 1<<N; ++j) dp[i][j] = oo;

    Precalc();
    dp[1][1] = 0;
    for(i = 1; i < N; ++i)
        for(j = 0; j < t[i].size(); ++j)
            for(mask = t[i][j], x = 1; x <= N; ++x)
            if(dp[x][mask] < oo)
                for(y = 1; y <= N; ++y)
                if( !((1<<y-1) & mask) )
                dp[y][mask | (1<<y-1)] = min(dp[y][mask | (1<<y-1)], dp[x][mask] + cost[x][y]);

    for(i = 1; i <= N; ++i) res = min(res, dp[i][(1<<N)-1] + cost[i][1]);
    if(res == oo) fprintf(fout,"Nu exista solutie\n");
    else fprintf(fout,"%d\n",res);


return 0;
}