#include <bits/stdc++.h>

using namespace std;

int cs[25][25];

int dp[1<<18][26];

set <int> s[25];

int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n,m,x,y,c;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y>>c;
        cs[x][y]=c;
        s[x].insert(y);
    }
    int lt=1<<(n-1);
    for(int i=0;i<lt;++i)
    {
        for(int j=0;j<n;++j)
        {
            dp[i][j]=INT_MAX;
        }
    }
    for(int i=1;i<n;++i)
    {
        if(cs[0][i]!=0)
        {
            dp[1<<(i-1)][i]=cs[0][i];
        }
    }
    for(int i=1;i<lt;++i)
    {
        for(int j=1;j<n;++j)
        {
            int nr=1<<(j-1);
            if(dp[i][j]!=INT_MAX)
            {
            if(i&nr)
            {
                for(auto a:s[j])
                {
                    int nn=1<<(a-1);
                   // cout<<i<<" "<<j<<" "<<a<<(i&nn)<<"       ";
                    if(cs[j][a]!=0 && (i&nn)==0 && a!=0)
                    {
                        if(dp[i+nn][a]>dp[i][j]+cs[j][a] && dp[i][j]!=INT_MAX)
                        {
                           // cout<<dp[i][j]+cs[j][a]<<"     ";
                            dp[i+nn][a]=dp[i][j]+cs[j][a];
                        }
                    }
                }
            }
            }
        }
    }
    int min=INT_MAX;
    int nx=1<<(n-1);
    for(int i=1;i<n;++i)
    {
        if(dp[nx-1][i]+cs[i][0]<min && cs[i][0]!=0)
        {
            min=dp[nx-1][i]+cs[i][0];
        }
    }
    if(min==INT_MAX)
    {
        cout<<"Nu exista solutie";
    }
    else
    {
        cout<<min;
    }
    return 0;
}