#include <bits/stdc++.h>

const int oo=1e9;

using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

#define Gmax 18

vector < int > G[Gmax];
int c[1 << Gmax][Gmax];
int d[Gmax][Gmax];

int main()
{
    memset(c, oo, sizeof(c));
    memset(d, oo, sizeof(d));
    int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        G[y].push_back(x);
        d[x][y]=z;
    }
    c[1][0]=0;
    for(int i=1;i<(1<<n);i++)
        for(int j=0;j<n; ++)
        {
            if(i&(1<<j)==0)
                continue;
            for(auto it=G[j].begin();it!=G[j].end();it++)
            {
                if(i&(1<<*it)==0)
                    continue;
                c[i][j]=min(c[i][j],c[i^(1<<j)][*it]+d[*it][j]);
            }
        }
    int sol=oo;
    for(auto it=G[0].begin();it!=G[0].end();++it)
        sol=min(sol,c[(1<<n)-1][*it]+ d[*it][0]);
    if(sol==oo)
        g<<"Nu exista solutie"<<'\n';
    else
        g<<sol;
    return 0;
}