#include <bits/stdc++.h>

#define NMax 18
#define INF 1000000000

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int N,M;
int cost=INF,T[(1<<NMax)+10][NMax+2];
vector <pair<int,int> > Graf[NMax+2];

int main()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        Graf[y].push_back(make_pair(x,c));
    }

    for(int i=0;i<(1<<NMax);i++)
        for(int j=0;j<N;j++)
            T[i][j]=INF;

    T[1][0]=0;
    for(int i=3;i<=(1<<N)-1;i+=2)
        for(int j=1;j<N;j++)
            if(i&(1<<j))
                for(vector<pair<int,int> >::iterator it=Graf[j].begin();it!=Graf[j].end();it++)
                    T[i][j]=min(T[i][j],T[i-(1<<j)][it->first]+it->second);

    for(vector<pair<int,int> >::iterator it=Graf[0].begin();it!=Graf[0].end();it++)
        cost=min(cost,T[(1<<N)-1][it->first]+it->second);

    if(cost!=INF)
        fout<<cost;
    else
        fout<<"Nu exista solutie";

    return 0;
}