#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int INF = 1000000005;
const int DIM = 18;

int n,m,x,y,c,DP[DIM][(1<<DIM)+2];

vector < pair<int,int> > G[DIM];

void Read()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
}

void Solve()
{
     for(int i=0;i<n;i++)
     {
         for(int mask=0;mask<(1<<n);mask++)
            DP[i][mask]=INF;
     }
     DP[0][1]=0;
     for(int mask=1;mask<(1<<n);mask++)
     {
         for(int nod=0;nod<n;nod++)
         {
             vector < pair<int,int> > ::iterator it;
             for(it=G[nod].begin();it!=G[nod].end();it++)
             {
                 int vecin=(*it).first;
                 int cost=(*it).second;
                 if(mask & (1<<vecin))
                    DP[nod][mask]=min(DP[nod][mask],DP[vecin][mask^(1<<nod)]+cost);
             }
         }
     }
}

void Print()
{
    int ans=INF;
    vector < pair<int,int> > ::iterator it;
    for(auto it : G[0])
    {
        int vecin=it.first;
        int cost=it.second;
        ans=min(ans,DP[vecin][(1<<n)-1]+cost);
    }
    if(ans==INF)
        fout<<"Nu exista solutie"<<'\n';
    else
        fout<<ans<<'\n';
}

int main()
{
    Read();
    Solve();
    Print();
}