#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int C[262150][20];
const int maxi=100000000;
int n,m;
int GR[20][20];
int x,y,z;
vector <int> V[20];
int cc(int inc,int j,int sf)
{
    if (C[j][sf]==-1)
    {
        C[j][sf]=maxi;
        for (size_t i=0; i<V[sf].size(); i++)
        {
            if (j & (1<<V[sf][i]))
            {
                if (V[sf][i] == inc && ((j ^ (1<<sf)) != (1<<inc)))
                    continue;
                C[j][sf] = min(C[j][sf], cc(inc, j ^ (1<<sf), V[sf][i]) + GR[V[sf][i]][sf]);
            }
        }
    }
    return C[j][sf];
}
int main()
{
    fin>>n>>m;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
                GR[i][j]=maxi;
    for (int i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        V[y].push_back(x);
        GR[x][y]=z;
    }
    int rez=maxi;
    for (int j=0 ;j<n; j++)
    {
        memset(C,-1,sizeof(C));
        C[1<<j][0]=0;
                for (size_t i=0; i<V[j].size(); i++)
            rez=min(rez,cc(j,(1<<n)-1,V[j][i])+GR[V[j][i]][j]);
    }
    if (rez==maxi)
        fout<<"Ne exista solutie";
    else
    fout<<rez;
    return 0;
}