#include <fstream>
#include <iostream>
#define INF 1000002

using namespace std;

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

int d[500000][19],a[19][19];
int main()
{
    int n,m,i,j,x,y,c,l;
    f>>n>>m;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>c;
        a[x+1][y+1]=c;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j && !a[i][j]) 
		a[i][j]=INF;

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

    d[1][1]=0;
    for(i=0;i<(1<<n);i++)
        for(j=1;j<=n;j++)
            if(i & (1<<(j-1)))
                for(l=1;l<=n;l++)
                    if((i & (1<<(l-1))) && l!=j)
                        if(d[i][j]>d[i-(1<<(j-1))][l]+a[l][j])
                            d[i][j]=d[i-(1<<(j-1))][l]+a[l][j];


    int sol=INF;
    for(i=2;i<=n;i++)
        if(d[(1<<n)-1][i]+a[i][1]<sol) 
		sol=d[(1<<n)-1][i]+a[i][1];

    if(sol==INF) 
	g<<"Nu exista solutie";
    else 
	g<<sol;
    return 0;
}