#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout("hamilton.out");
int n,m;
int A[19][19];
int Dp[1<<18+1][20];
const int INF=2000000000;
int main()
{
    fin>>n>>m;
    int mmax=(1<<n) - 1;
    for (int j=0; j<n; j++) {
        for(int i=0; i<n; i++)
            A[i][j]=INF; // la inceput, nu putem trece de la niciun nod la niciun nod
        for(int i=0;i<=mmax;i++)
            Dp[i][j]=INF; // initializez DP-ul cu infinit
    }
    for (int i=0; i<m; i++) {
        int a,b,c;
        fin>>a>>b>>c;
        A[a][b]=c; // setez matricea de costuri
    }
    //nota: alegem nodul 0 ca inceput
    Dp[1][0] = 0; // caz elementar in care avem doar nodul 0 in ciclu
    for(int mask=3;mask<=mmax;mask+=2)//nota: includem mereu elementul 0
    {
        for(int i=1;i<n;i++)
        {
            if(~mask&(1<<i)) continue;

            //parcurgem toate arcele (j,i) care exista
            for(int j=0;j<n;j++)
            {
                if(A[j][i]==INF) continue;

                //in cazul in care am gasit un drum mai scurt
                //0->...->j->i decat 0->...->i pe care l-am avut
                Dp[mask][i] = min(Dp[mask&~(1<<i)][j]+A[j][i], Dp[mask][i]);
            }
        }
    }

    //calculez solutia finala
    int final=INF;
    for(int i=1;i<n;i++)
    {
        if(A[i][0] == INF) continue;
        final=min(final,Dp[mmax][i]+A[i][0]);
    }

    if(final==INF)
        fout<<"Nu exista solutie";
    else
        fout<<final;

    return 0;
}