#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;

int dp[(1<<19)+10][20],cost[20][20],n,m;
vector<int> G[20];

#define INF 0x3f3f3f3f

int main()
{
    freopen("hamilton.in","rt",stdin);
    freopen("hamilton.out","wt",stdout);

    cin>>n>>m;

	for (int i=0;i<n;++i)
		for (int j=0;j<n;++j)
            cost[i][j] = INF;

	for (int i=1;i<=m;++i)
	{
		int x, y;
		cin>>x>>y;
		G[y].push_back(x);
		cin>>cost[x][y];
	}

	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 i=0;i< 1<<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(i&(1<<j))
            {
                for(int k=0;k<G[j].size();++k)
                {
                    if(i&(1<<G[j][k]))//daca vecinul lui j este in configuratie (bitul de pe poz lui in configuratia i este 1)
                    {
                        //cerr<<G[j][k]<<' ';
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][G[j][k]] + cost[G[j][k]][j]);//

                    }
                }
            }
        }
    }
    int minim=INF;
    for(int i=0;i<G[0].size();++i)
    {
        minim=min(minim,dp[(1<<n)-1][G[0][i]]+cost[G[0][i]][0]);
    }

    if(minim==INF)
        cout<<"Nu exista solutie"<<'\n';
    else
        cout<<minim<<'\n';



    return 0;
}