#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int inf=0x3f3f3f3f;
int cost[20][20],C[263000][20];
vector<int>A[20];
int calc(int start,int conf,int last)
{
    if(C[conf][last]==-1)
    {
        C[conf][last]=inf;
        for(unsigned j=0;j<A[last].size();j++)
        {
            if(conf&(1<<A[last][j]))
            {
                if(A[last][j]==start && ((conf^(1<<last))!=(1<<start))) continue;
                C[conf][last]=min(C[conf][last],calc(start,conf^(1<<last),A[last][j])+cost[A[last][j]][last]);
            }
        }
    }
    return C[conf][last];
}
int main()
{
    int n,m,a,b;
    fin>>n>>m;
    memset(cost,inf,sizeof(cost));
    while(m--)
    {
        fin>>a>>b;
        fin>>cost[a][b];
        A[b].push_back(a);
    }
    int sol=inf;
        memset(C,-1,sizeof(C));
        C[1][0]=0;
        for(unsigned j=0;j<A[0].size();j++)
        {
            sol=min(sol,calc(0,(1<<n)-1,A[0][j])+cost[A[0][j]][0]);
        }
    if(sol==inf) fout<<"Nu exista solutie";
    else fout<<sol;
}