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

    return 0;
}