#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const short Nmax=19;
const int inf=100000000;
int dp[Nmax][1<<Nmax],cost[Nmax][Nmax],valmax,n,m;
vector<int>L[Nmax];
queue<pair<int,int> >Q;
int main()
{
    int x,y,c,stare,varf;
    fin>>n>>m;
    valmax=(1<<n)-1;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cost[i][j]=inf;
    for(int i=0; i<n; i++)
        for(int j=0; j<=valmax; j++)
            dp[i][j]=inf;
    while(m--)
    {
        fin>>x>>y>>c;
        cost[x][y]=c;
        L[x].push_back(y);
    }
    stare=1;
    dp[0][stare]=0;
    Q.push({0,stare});
    while(!Q.empty())
    {
        varf=Q.front().first;
        stare=Q.front().second;
        Q.pop();
        for(auto i:L[varf])
        {
            if((stare&(1<<i))==0)
            {
                if(dp[i][(stare|(1<<i))]>dp[varf][stare]+cost[varf][i])
                {
                    dp[i][(stare|(1<<i))]=dp[varf][stare]+cost[varf][i];
                    Q.push({i,(stare|(1<<i))});
                }
            }
        }
    }
    int sol=inf;
    for(int i=0; i<n; i++)
        sol=min(sol,dp[i][valmax]+cost[i][0]);
    if(sol==inf)
        fout<<"Nu exista solutie\n";
    else fout<<sol<<"\n";
    fin.close();
    fout.close();
    return 0;
}