#include <bits/stdc++.h>
#define Xp 17000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,x,y,c,bit,i,j,cost[18][18],d[18][1<<18];
int main()
{
    f>>n>>m;
    while(m--)
    {
        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;
}