#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int INF=1e9;
int dp[262165][20];
int v[20][20];
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            v[i][j]=INF;
            v[j][i]=INF;
        }
    }
    for(int i=0;i<m;i++)
    {
        int l,r,c;
        fin>>l>>r>>c;
        v[l][r]=c;
    }
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
        {
            dp[i][j]=INF;
        }
    }
    dp[1][0]=0;
    for(int mask=1;mask<(1<<n);mask++)
    {
        for(int bit=0;bit<n;bit++)
        {
            if(mask & (1<<bit))
            {
                for(int i=0;i<n;i++)
                {
                    if(!(mask & (1<<i)))
                    {
                        dp[(mask | (1<<i))][i]=min(dp[(mask | (1<<i))][i],dp[mask][bit]+v[bit][i]);
                    }
                }
            }
        }
    }
    int ans=INF;
    for(int i=0;i<n;i++)
    {
        if(ans>dp[(1<<n)-1][i]+v[i][0])
        {
            ans=dp[(1<<n)-1][i]+v[i][0];
            //cout<<i<<' ';
        }
    }
    if(ans==INF) fout<<"Nu exista solutie";
    else fout<<ans;
    return 0;
}