#include<fstream>
#include<vector>
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int Nmax=20;
const int oo=1<<30;
const int Maxx=1000000;

int n,m;
int Cost[Nmax][Nmax];
int C[Maxx][Nmax];
vector<int>v[Nmax];

inline void Citire()
{
    int i,j,x,y;
    fin>>n>>m;
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            Cost[i][j]=oo;
    for (i=1;i<=m;i++)
        {
            fin>>x>>y;
            v[y].push_back(x);
            fin>>Cost[x][y];
        }
    for (i=0;i<(1<<n);i++)
        for (j=0;j<n;j++)
            C[i][j]=oo;
}

inline void DP()
{
    int i,j,k,len,sol;
    C[1][0]=0;
    for (i = 0; i < (1<<n) ; i++)
        for (j=0;j<=n;j++)
            if (i & (1<<j))
                {
                    len=v[j].size();
                    for (k=0;k<len;k++)
                        if (i & (1<<v[j][k]))
                            C[i][j]=min(C[i][j],C[i^(1<<j)][v[j][k]]+Cost[v[j][k]][j]);
                }
    sol=oo;
    len=v[0].size();
    for (j=0;j<len;j++)
        sol=min(sol,C[(1<<n)-1][v[0][j]]+Cost[v[0][j]][0]);
    if (sol!=oo) fout<<sol;
    else fout<<"Nu exista solutie";
    fout<<"\n";
}

int main()
{
    Citire();
    DP();
    return 0;
}