#include <fstream>
#include <vector>
#include <set>

using namespace std;

#define NAGY 99999999

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

int n,i,a,b,c,x[1<<18][18],mini,j,k,m;
struct adat
{
    vector<pair<int,int> >ut;
};
vector<adat>csp;

int main()
{
    cin>>n>>m;
    csp.resize(n);
    for(i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        csp[a].ut.push_back({b,c});
    }

    /*for(i=1;i<=n;++i)
    ut[i][i]=NAGY;*/

    for(i=0;i< 1<<(n+1);++i)
    for(j=0;j<=n;++j)
    x[i][j]=NAGY;

    x[1][0]=0;

    for(i=1;i< (1<<n);++i)
    for(j=0;j<n;++j)
    if(i & (1<<j) )
    {
        for(auto k : csp[j].ut)
        if(i & (1<<k.first) )
        x[i][j]=min(x[i][j],x[i^ (1<<j)][k.first]+k.second);
    }

    mini=NAGY;

    for(auto e : csp[0].ut)
    mini=min(mini, x[(1<<n)-1][e.first]+e.second);

    if(mini!=NAGY) cout<<mini<<"\n";
    else cout<<"Nu exista solutie\n";

    return 0;
}