#include <fstream>
#include <cstring>
#define NMAX 18
 
using namespace std;
 
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
 
int v[NMAX][NMAX];
int N,M,minim;
int D[1<<NMAX][NMAX];
int main() {
    fin>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y,c;
        fin>>x>>y>>c;
        v[x][y]=c;
    }
    memset(D,0x3f3f3f3f,sizeof(D));
    minim=0x3f3f3f3f;
    D[1][0]=0;
    for(int mask=3;mask<(1<<N);mask+=2){
        for(int i=1;i<N;i++){
            if ((mask >> i) & 1) {
                // are sens sa calculez D[mask][i] inn functie de D[mask - (1<<i)][ceva care e inca 1 in mask-(1<<i))]
                for (int j=0;j<N;j++)
                    if ((j != i) && ((mask >> j) & 1) && v[j][i] != 0)
                        D[mask][i] = min(D[mask][i], D[mask^(1<<i)][j] + v[j][i]);
 
            }
        }
    }
    for(int i=1;i<N;i++)
        if(v[i][0]!=0)
            minim=min(D[(1<<N)-1][i]+v[i][0],minim);
    if(minim==0x3f3f3f3f){
        fout<<"Nu exista solutie";
        return 0;
    }
    fout<<minim<<"\n";
    return 0;
}