#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define INF 100000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,x,y,z,dist[19][262150],cost[19][19]={INF},min1cost=INF;
vector <vector <int>> v(19);
int calc (int viz,int last)
{
    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];
}
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;
}