#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define INF 100000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,x,y,z,dist[19][(1<<18)+1],cost[20][20]={INF},min1cost=INF;
vector <vector <int>> v(19);
queue <pair<int,int>> q;
/*void searcht (int cur,int viz)
{
    q.push(make_pair((1<<start),start));
    while (!q.empty())
    {
        int viz=q.front().first,cur=q.front().second;
      //  cout<<cur<<'\n';
       // cout<<viz<<' '<<cur<<' '<<dist[cur][viz]<<'\n';
        if (viz==(1<<(n))-1)
        {
            //cout<<"DA";
            int ok=0;
            for (int j=0; j<v[cur].size() && ok==0; j++)
            {
                if (v[cur][j]==start)
                {
                    ok=1;
                    if (dist[start][viz]!=0)
                    dist[start][viz]=min(dist[start][viz],dist[cur][viz]+cost[cur][j]);
                    else dist[start][viz]=dist[cur][viz]+cost[cur][j];
                }
            }
        }
        else
        {
        for (int j=0; j<v[cur].size(); j++)
        {
            //cout<<!(viz & (1<<v[cur][j]))<<'\n';
            if (!(viz & (1<<v[cur][j])) && (dist[v[cur][j]][viz+(1<<v[cur][j])]>dist[cur][viz]+cost[cur][j] || dist[v[cur][j]][viz+(1<<v[cur][j])]==0))
            {

                dist[v[cur][j]][viz+(1<<v[cur][j])]=dist[cur][viz]+cost[cur][j];
               // cout<<v[cur][j]<<' '<<dist[v[cur][j]][viz+(1<<v[cur][j])]<<'\n';
                q.push(make_pair(viz+(1<<v[cur][j]),v[cur][j]));
            }
        }
        }
        //cout<<'\n';
        q.pop();
    }
}*/
int calc (int viz,int last)
{
    int minopt=INF;
    //cout<<viz<<' '<<last<<'\n';
    if (dist[last][viz]==-1)
    {
        dist[last][viz]=INF;
    for (int j=0; j<v[last].size(); j++)
    {
        if (viz & (1<<v[last][j]))
        {
            if ((v[last][j]==0 && viz!=(1<<last)+1))
            {
                //dist[v[last][j]][viz-(1<<v[last][j])]=;

            }
            else dist[last][viz]=min(dist[last][viz],calc(viz-(1<<last),v[last][j])+cost[v[last][j]][last]);
         //   minopt=min(minopt,dist[v[last][j]][viz-(1<<v[last][j])]+cost[last][v[last][j]]);
        }
    }
    }
    return dist[last][viz];
    //else if (viz==0)
    //{
      //  return 1;
    //}
}
int main()
{
    //cout<<sizeof(dist)/1000000;
    f>>n>>m;
    for (int i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        v[y].push_back(x);
        cost[x][y]=z;
    }
    memset(dist,-1,sizeof(dist));
    dist[0][1]=0;
    for (int start=0; start<v[0].size(); start++)
    {
        int next=v[0][start],test=calc((1<<n)-1,next)+cost[next][0];
        //cout<<test<<' '<<cost[next][0]<<'\n';
        min1cost=min(min1cost,test);
        /*for (int j=0; j<n; j++)
        {
            memset(dist[j],0,sizeof(dist[j]));
        }
        searcht(start);
       // cout<<'\n';

        //cout<<min1cost<<'\n';
        if (dist[start][(1<<(n))-1]>0)
                min1cost=min(min1cost,dist[start][(1<<(n))-1]);*/
    }
    if (min1cost!=INF)
    g<<min1cost;
    else
    {
        g<<"Nu exista solutie";
    }
    return 0;
}