#include <bits/stdc++.h>
#define inf 0x7F7F7F7F
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,x,y,z,cost,vecin,nod,s,i,all,d[18][(1<<17)],nextStare,sol,j,v,ns;
vector < pair<int,int> > L[18],L2;
int main()
{
    fin>>n>>m;

    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        L[x].push_back({y,z});
        if(!y)
        L2.push_back({x,z});
    }
    all=(1<<(n-1))-1;
    memset(d,127,sizeof(d));
    d[0][0]=0;
    for(s=0; s<=all; s++)
    {
        for(i=0; i<n; i++)
        {
            if(d[i][s]!=inf)
            {
                for(j=0; j<L[i].size(); j++)
                {
                    v=L[i][j].first;
                    if(!(s&(1<<(v-1)))&& v)
                    {
                        ns=(s|(1<<(v-1)));
                        d[v][ns]=min(d[v][ns],d[i][s]+L[i][j].second);

                    }
                }
            }
        }

    }
    sol=inf;
    for(i=0;i<L2.size();i++)
      sol=min(sol,d[L2[i].first][all]+L2[i].second);
    if(sol!=inf)
    fout<<sol;
    else
   fout<<"Nu exista solutie";
}