#include<cstdio>
#include<vector>
#include<cstring>

#define INF 0x3f3f3f3f
#define MAX_SIZE 20
#define LMAX (1<<18)+10
#define min(a,b) ((a)<(b)?(a):(b))

FILE *f=fopen("hamilton.in","r");
FILE *g=fopen("hamilton.out","w");

using namespace std;

vector<int> G[MAX_SIZE];

int sol=INF;
int cost[MAX_SIZE][MAX_SIZE];
int c[LMAX][MAX_SIZE];
int n,m;


void read( void )
{
    fscanf(f,"%d%d",&n,&m);
    memset(cost,INF,sizeof(cost));
    memset(c,INF,sizeof(c));
    for(int i(1); i <= m ; i++)
    {
        int a,b,c;
        fscanf(f,"%d%d%d",&a,&b,&c);
        G[b].push_back(a);
        cost[a][b]=c;
    }
    fclose(f);
}
void solve ( void )
{
    c[1][0]=0;

    for(int i(0); i < (1<<n); ++i )
        for(int ii(0); ii <n ;++ii )
              if(i & (1<<ii) )//daca exista nodul ii in lant
          for(int k(0); k < G[ii].size(); ++k)
              if(i & (1<<G[ii][k]) )  //le aleg doar pe cele care fac parte din lant
          c[i][ii]=min(c[i][ii],cost[G[ii][k]][ii]+c[i^(1<<ii)][G[ii][k]]);//i^(1<<ii) eleminim nodul curent si raman doar celelalte

   for(int i(0) ; i < G[0].size() ; ++i )
    sol=min( sol , cost[G[0][i]][0] + c[(1<<n)-1][G[0][i]]);
}
void write( void )
{
    if(sol!=INF)
    fprintf(g,"%d",sol);
    else
    fprintf(g,"Nu exista solutie");
    fclose(g);
}


int main( void )
{
    read();
    solve();
    write();
    return 0;

}