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

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

const int N=20;
const int inf=0x3f3f3f3f;

struct nod
{
	int varf,cost;
};

vector <nod> a[N];

int d[(1<<N)][N];
int v[N];
int n,m;


inline int min(int a,int b)
{
	return a<b ? a:b;
}


void hamilton()
{
	int i,j;

    for(i=1;i<=n;i++)
        for(j=0;j<=n;j++)
            d[i][j]=inf;
    d[1][0]=0;

	for(i=2;i<=(1<<n);i++)
		for(j=0;j<n;j++)
		{
			if(i&(1<<j))
			{
				for(vector<nod> :: iterator k=a[j].begin(); k!=a[j].end();k++)
					if(i&(1<<((*k).varf)))
                        d[i][j]=min(d[i][j],d[i^(1<<j)][(*k).varf]+(*k).cost);
			}

			else
				d[i][j]=inf;
		}
}

int main()
{
	int minim=inf,i,j,x,y,c;
	in>>n>>m;

	for(i=1;i<=n;i++)
		v[i]=inf;

	while(m--)
	{
		in>>x>>y>>c;
		a[y].push_back((nod) {x,c});
		if(y==0)
			v[i]=c;

	}

	hamilton();

	for(i=1;i<=(1<<n)-1;i++)
	{
        for(j=0;j<n;j++)
            out<<d[i][j]<<"\t";
        out<<"\n";
	}
	for(i=1;i<=n;i++)
	{
		if(d[(1<<n)-1][i]+v[i]<minim)
			minim=d[(1<<n)-1][i]+v[i];
	}

	if(minim!=inf)
		out<<minim;
	else
		out<<"Nu exista solutie";

	return 0;
}