#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)+1][19],mini,j,k,m,hossz[19][19];
/*struct adat
{
    vector<int>ut;
};*/
vector<int>csp[19];

int main()
{
    cin>>n>>m;

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

//    csp.resize(n);

    for(i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        csp[b].push_back(a);
        hossz[a][b]=c;
    }


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

    x[1][0]=0;

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

    /*for(i=0;i< (1<<n);++i)
    {
        for(j=0;j<n;++j)
            cout<<x[i][j]<<" ";
        cout<<'\n';
    }*/


    mini=NAGY;

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

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

    return 0;
}