#include <iostream>
#include <cstdio>
#include <vector>
#define maxi 1000000000
using namespace std;
FILE* f=fopen("hamilton.in","r");
FILE* g=fopen("hamilton.out","w");
int n,m,cost[20][20],c[262150][19],x,y,sol=maxi;
vector <int> a[20];
int main()
{
    fscanf(f,"%d%d",&n,&m);

    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
        if(i<n)
    {
        cost[i][j]=maxi;
        c[i][j]=maxi;
    }
    else c[i][j]=maxi;
    for(;m;m--)
    {
        fscanf(f,"%d%d",&x,&y);
        a[y].push_back(x);
        fscanf(f,"%d",&cost[x][y]);
    }
    c[1][0]=0;
    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
            if(i&(1<<j))
                for(int k=0;k<a[j].size();++k)
                    if(i&(1<<a[j][k]))
                        c[i][j]=min(c[i][j], c[i^(1<<j)][a[j][k]]+cost[a[j][k]][j]);
    for(int i=0;i<a[0].size();i++)
        sol=min(sol,c[(1<<n)-1][a[0][i]]+cost[a[0][i]][0]);
    if(sol!=maxi)
        fprintf(g,"%d",sol);
    else fprintf(g,"%s","Nu exista solutie");
    return 0;
}