#include <fstream>
#include <iostream>
#define INF 1000000000
 
using namespace std;
 
ifstream f("hamilton.in");
ofstream g("hamilton.out");
 
int d[(1000000)][1000000],a[1000000][1000000];
 
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;
}