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

using namespace std;

const int N=19;
vector<pair<int,int>> g[N];
int dp[1<<(N)],n,m,atinsmax;
set<pair<pair<int,int>,int>> s;
/// cost, nod

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin>>n>>m;
    int i,j,x,y,c,nod,masca;
    for(x=0; x<m; x++)
    {
        fin>>i>>j>>c;
        g[i].push_back({j,c});
    }
    for(i=0; i<n; i++)
        s.insert({{0,i},1<<i});
    while(!s.empty())
    {
        c=(*s.begin()).first.first;
        nod=(*s.begin()).first.second;
        masca=(*s.begin()).second;
        s.erase(s.begin());
        for(auto el:g[nod])
        {
            if(masca&(1<<el.first))continue;
            if(!dp[masca|(1<<el.first)]
                    ||el.second+dp[masca]<dp[masca|(1<<el.first)])
            {
                dp[masca|(1<<el.first)]=el.second+dp[masca];
                s.insert({{dp[masca|(1<<el.first)],el.first},masca|(1<<el.first)});
               if( masca|(1<<el.first) ==(1<<n)-1)atinsmax=1;
            }

        }


    }
    if(atinsmax)
    {
        fout<<dp[(1<<n)-1];
    }
    else fout<<"Nu exista solutie";

    return 0;
}