#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;

const int INF=1000000000;
int n,m1;
vector<int> m[20];
int dp[1048576][20];
int cost[20][20];
int change;
int previ[20];

int calc(int mask,int v)
{
  //  cout<<mask<<' '<<v<<'\n';
    int i;
    if( dp[mask][v]!=INF)
            return dp[mask][v];
    dp[mask][v]=INF-1;
    for(vector<int>::iterator it=m[v].begin();it!=m[v].end();it++)
    {
        i=*it;
       // cout<<i<<'\n';
        if(i!=v && (( mask>>i)&1) )
        {
            int k=calc(mask^(1<<v),i);
           // cout<<"k: "<<k<<'\n';
            if(k==0) previ[i]=INF;
            if(k==0 && cost[i][0]==0) continue;
            if(dp[mask][v]>k+cost[v][i])
            {
                dp[mask][v]=k+cost[v][i];
                change=i;
                previ[v]=i;
               // cout<<"do"<<i<<"\n";
            }
          //  cout<<"dp: "<<dp[mask][v]<<'\n';
        }
    }
    return dp[mask][v];
}

int main()
{
    ifstream t1("hamilton.in");
    ofstream t2("hamilton.out");
    t1>>n>>m1;
    int i,j,a,b,c;
    for(i=1;i<=m1;i++)
    {
        t1>>a>>b>>c;
        cost[a][b]=c;
        m[a].push_back(b);
    }
    for(i=0;i<1<<n;i++)
        for(j=0;j<n;j++) dp[i][j]=INF;
    for(j=0;j<n;j++)
        dp[1<<j][j]=(j==0?INF-1:0);
    int sol=calc( (1<<n)-1,0);
    while(previ[change]!=INF)
    {
        //cout<<change<<'\n';
        change=previ[change];
    }
    if(sol==INF) t2 << "Nu exista solutie" << endl;
    else t2<<sol+cost[change][0];
    return 0;
}