#include<bits/stdc++.h>
#define X 17000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int e[18][18],d[18][1<<18],n,m,x,y,c,b,i,j,s;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
        f>>x>>y>>c,e[x][y]=c;
    memset(d,X,sizeof d),d[0][1]=0;
    for(b=1;b<(1<<n);++b)
        for(i=0;i<n;++i)
            if(b&(1<<i))
                for(j=0;j<n;++j)
                    if(e[i][j]&&!(b&(1<<j)))
                        d[j][b|(1<<j)]=min(d[j][b|(1<<j)],d[i][b]+e[i][j]);
    for(s=X,i=0;i<n;++i)
        if(e[i][0])
            s=min(s,d[i][(1<<n)-1]+e[i][0]);
    s<X?g<<s:g<<"Nu exista solutie";
    return 0;
}