#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[(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 Solve()
{
     for(int i=0;i<n;i++)
     {
         for(int mask=0;mask<(1<<n);mask++)
            DP[mask][i]=INF;
     }
     DP[1][0]=0;
     for(int mask=1;mask<(1<<n);mask+=2)
     {
         for(int nod=0;nod<n;nod++)
         {
             for(auto it : G[nod])
             {
                 int vecin=it.first;
                 int cost=it.second;
                 if(mask & (1<<vecin))
                    DP[mask][nod]=min(DP[mask][nod],DP[mask^(1<<nod)][vecin]+cost);
             }
         }
     }
}

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

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