#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 18
#define ll long long
#define inf (1<<28)

int n, m, a[nmax][nmax], c[nmax][nmax], dp[(1<<nmax)][nmax];

void citeste(){
    f >> n >> m;
    int x, y, z;
    for(int i=1; i<=m; ++i){
        f >> x >> y >> z;
        a[x][y] = 1;
        c[x][y] = z;
    }
}

void rezolva(){
    // dp[conf][i] = costul minim a unui lant ce contine nodurile corespunzatori bitilor de 1 din conf si se termina in nodul i
    // nodurile sunt de la 0 la n-1
    int lim = (1<<(n-1));
    for(int i=0; i<lim; ++i){
        for(int j=0; j<n; ++j){
            dp[i][j] = inf;
        }
    }

    for(int i=0; i<n; ++i) dp[1<<i][i] = 0;
    for(int conf=3; conf<lim; ++conf){
        for(int j=0; j<n; ++j){
            if (conf &(1<<j) ){// vreau sa termin in j
                int precConf = conf - (1<<j);
                for(int k=0; k<n; ++k){// acum vreau sa il continui pe k
                    if (j == k) continue;
                    if (a[k][j] != 0 && ( conf &(1<<k) ) != 0 ){// daca am muchie intre k si j si daca k face parte din conf
                        dp[conf][j] = min(dp[conf][j], dp[precConf][k] + c[k][j]);
                    }
                }
            }
        }
    }

    // acum vreau sa inchid ciclul; deci daca am ciclu nu conteaza nodul de pornire; e irelevant pt ca tot timpul voi putea sa inchid ciclul
    // daca el intr-adevar exista
    // => il aleg pe 0 ca si pct de plecare
    int Min = inf;// pt ca nu exista
    // acum inchid ciclul
    for(int i=1; i<n; ++i){
        if (a[i][0] != 0){// am muchie de la i la 0
            Min = min(Min, dp[lim-1][i] + c[i][0]);
        }
    }
    if (Min == inf){
        g << "Nu exista solutie" << "\n";
    }else {
        g << Min << "\n";
    }

}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}