#include <fstream>

using namespace std;

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

int nrVarfuri, nrMuchii;
const int N = 18;
const int N2 = 262144;
const int INF = 18000001;
int d[N2+1][N+1];
int mat[N+1][N+1];

int minim(int a , int b){return a<b ? a : b ; }

int main()
{
    in>>nrVarfuri>>nrMuchii;
    for(int i=1; i<=nrMuchii; i++){
        int x, y, cost;
        in>>x>>y>>cost;
        mat[x][y] = cost;
    }

    for(int i=1;i<nrVarfuri;i++){
        d[1][i]=INF;
    }

    int nrPerm = (1<<nrVarfuri) - 1;

    for(int i=3;i<=nrPerm;i+=2){
        d[i][0]=INF;
        for(int j=1;j<nrVarfuri;j++){
            d[i][j] = INF ;
            int j2 = (1<<j);
            if( i & j2 ) {
                int iprim = i ^ j2 ;
                for(int k = 0 ; k <nrVarfuri ; k++ ){
                    int k2 = (1<<k);
                    if(mat[k][j]!=0 && (iprim & k2) && j!=k ){
                        d[i][j] = minim ( d[i][j], d[iprim][k] + mat[k][j] );
                    }
                }
            }
        }
    }

    int rez = INF;
    for(int i=1;i<nrVarfuri;i++){
        if(mat[i][0]!=0){
            rez = minim(rez, d[nrPerm][i] + mat[i][0]);
        }
    }
    if(rez == INF ){
        out<<"Nu exista solutie";
    } else {
        out<<rez;
    }
    return 0;
}