#include <stdio.h>
#include <iostream>
#include <cmath>
#include <algorithm>
FILE *f, *g;
using namespace std;
struct graf
{
    int node, next;
}v[400];
int dp[1<<19][19], cost[19][19];
int start[20];
int n,m;
void read()
{   int x,y,c,k=0;
    fscanf(f,"%d %d",&n,&m);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j]=9999999;
    for(int i=1; i<=m; i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        v[++k].node=x;
        v[k].next=start[y];
        start[y]=k;
        cost[x][y]=c;
    }
}
int minim(int a, int b)
{
    return a<b ? a:b;
}
void solve()
{
    for(int i=0; i< 1<<n; i++)
        for(int j=0; j<n; j++)
            if(i & (1<<j))
                for(int k=start[j]; k; k=v[k].next)
                    if(i & (1<<v[k].node))
                        if(dp[i][j]<dp[i - (1<<j)][v[k].node]+cost[v[k].node][j])
                            dp[i][j]=dp[i - (1<<j)][v[k].node]+cost[v[k].node][j];
    int mini=999999999;
    for(int i=start[0]; i; i=v[i].next)
        mini=minim(mini, dp[(1<<n)-1][v[i].node] + cost[v[i].node][0]);

    if(mini==999999999)
        fprintf(g,"Nu exista solutie");
    else
        //cout<<mini;
    fprintf(g,"%d",mini);
}
int main()
{
    f=fopen("hamilton.in","r");
    g=fopen("hamilton.out","w");
    read();
    solve();
    fclose(f);
    fclose(g);
    return 0;
}