#include<fstream>
#include<vector>
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n,sol,a,b,i,j,x,k,m;
int dp[1<<20][20];
vector<int> v[20];
int cost[20][20];

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b;
        v[b].push_back(a); // a intra in b
        fin>>cost[a][b];
    }
    for(i=0;i<1<<n;++i)
        for(j=0;j<n;++j)
        dp[i][j]=1<<30;

    dp[1][0]=0;
    for(i=1;i<1<<n;++i)
        for(j=0;j<n;++j)
            if(i&(1<<j)) // configuratia actuala il contine pe j
            {
                for(k=0;k<v[j].size();++k)
                {
                    x=v[j][k];// un nod care intra in j
                    if(i&(1<<x)) // configuratia actuala il contine pe x
                    {
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][x]+cost[x][j]);
                    }
                }
            }

        sol=1<<30;
        for(i=0;i<v[0].size();++i)
        {
            sol=min(sol,dp[(1<<n)-1][v[0][i]]+cost[v[0][i]][0]);
        }
        if(sol!=1<<30)
        fout<<sol;
        else
        fout<<"Nu exista solutie";







    return 0;
}