#include<bits/stdc++.h>
#define INF 1000000000
#define DIM (1<<18)
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int N,M,i,C[DIM][20],Cost[20][20],j;
vector<int>G[DIM];
int calc(int conf,int last)
{
    if(C[conf][last]==-1)
    {
        C[conf][last]=INF;
        for(size_t i=0;i<G[last].size();i++)
            if(conf and (1<<G[last][i]) and !(G[last][i]==0 and conf!=(1<<last)+1))
                C[conf][last]=min(C[conf][last],calc(conf xor (1<<last),G[last][i])+Cost[G[last][i]][last]);
    }
    return C[conf][last];
}
int main()
{
    in>>N>>M;
    int S=INF;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            Cost[i][j]=INF;
    for(i=0;i<M;i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        G[b].push_back(a);
        Cost[a][b]=c;
    }
    memset(C,-1,sizeof(C));
    C[1][0]=0;
    for(size_t i=0;i<G[0].size();i++)
        S=min(S,calc((1<<N)-1,G[0][i])+Cost[G[0][i]][0]);
    (S==INF)?out<<"Nu exista solutie":out<<S;
}