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

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

const int N=20;
const int INF=20000000;
int d[1 << N][N],C[N][N],n,m;
/*
submultimile multimii {1,2,3}:
multimea vida -> (0,0,0) -> 0
{1} -> (1,0,0) -> 1
{1,2} -> (1,1,0) -> 3
{1,2,3} -> (1,1,1) -> 7
{2} -> (0,1,0) -> 2
...

i va codifica o submultime:
    j apartine i <=> ((1 << j) & i) != 0
    setez bitul j al lui i la 0: i ^= (1 << j)
    setez bitul j al lui i la 1: i |= (1 << j)

d[i][j] = costul celui mai ieftin drum care trece prin varfurile codificate prin i
d[i][j] = min{d[ij][k] | 0<=k<n si k apartine i} unde ij = i ^ (1<<j)
d[i][j] = INF daca j nu apartine i
*/
void citire()
{
    int x,y,c,i;
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>c;
        C[x][y]=c;
    }
}

void ciclu()
{
    int k,i,j;
    for(i=1; i<=(1 << n); i++)
        for (j = 0; j < n; j++)
        {
            d[i][j] = INF;
        }
    d[1][0] = 0;
    for(i=3; i < (1 << n); i+=2)
        for(j=0; j<n; j++)
            if(((1 << j) & i)!=0)
            {
                for(k=0; k<n; k++)
                {
                    if(C[k][j]>0 && ((1 << k) & i)!=0)
                        d[i][j]=min(d[i][j],d[i ^ (1 << j)][k]+C[k][j]);
                }
            }
            else
                d[i][j]=INF;

}
int main()
{
    int i,j,rez;
    citire();
    ciclu();
    /* for(i=1; i<=1 << n; i++)
     {
         for(j=0; j<n; j++)
             out<<d[i][j]<<"\t";
         out<<'\n';
     }
     */
     rez=INF;
    for(i=1; i<n; i++)
    {
        if(C[i][0]!=0)
            rez=min(rez,C[i][0]+d[(1 << n)-1][i]);
    }
    if(rez>=INF)
        out<<"Nu exista solutie";
    else
        out<<rez;
    return 0;
}