#include<fstream>
#include<cstdio>
#include<vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int dp[(1<<20)][20];
int adi[20][20];
int cost[20][20];
int n,m,i,j,a,b,c,minim=1e9;
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        adi[a][b]=1;
        cost[a][b]=c;
    }
    for(int msk=0;msk<(1<<n);++msk)
    {
        for(j=0;j<n;++j)
            dp[msk][j]=1e9;
    }
    dp[(1<<0)][0]=0;
    for(int msk=1;msk<(1<<n);++msk)
    {
        int cnt=__builtin_popcount(msk);
        for(j=0;j<n;++j)
        {
            if(msk & (1<<j))
            {
                for(i=0;i<n;++i)
                {
                    if(cnt<n)
                    {
                        if(adi[i][j]==1 && (msk & (1<<i)))
                            dp[msk][j]=min(dp[msk][j],dp[msk-(1<<j)][i] + cost[i][j]);
                    }
                    else
                    {
                        if(adi[i][j]==1 && (msk & (1<<i)) && adi[j][0]==1)
                            dp[msk][j]=min(dp[msk][j],dp[msk-(1<<j)][i] + cost[i][j] + cost[j][0]);
                    }
                }
            }
        }
    }
    for(i=0;i<n;++i)
    {
        minim=min(minim,dp[(1<<n)-1][i]);
    }
    if (minim == 1e9){
      fout << "Nu exista solutie";
      return 0;
    }
    fout<<minim;
    return 0;
}