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

using namespace std;

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

const int INF = (1<<30);
const int DIM = 18;

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

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 SetArray()
{
    for(int i=0;i<n;i++)
        for(int mask=0;mask<(1<<n);mask++)
            DP[mask][i]=INF;
    DP[1][0]=0;
}

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

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

int main()
{
    Read();
    SetArray();
    FindCycle();
    Print();
}