#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 Exp ( (1<<18)+1)
#define inf (1<<30)

int n, m, cost[nmax][nmax], dp[Exp][nmax];

void citeste(){

	f >> n >> m;

	for(int i=1; i<=m; ++i){
        int x, y, c;
        f >> x >> y >> c;
        cost[x][y] = c;
	}

}

void rezolva(){

    //trebuie sa determin un ciclu de cost minim; in ciclu sa apara fiecare nod o singura data;/
    // nodul de start nu are relevanta => gasesc un drum de cost minim intre toate nodurile; imi fixez un nod de start si apoi la final caut un alt nod
    //care sa aiba distanta minim de la el si pana la nodul de start
    //noduril sunt indexate de la 0 , n-1


    for(int conf=0; conf<(1<<n); ++conf)
        for(int j=0; j<n; ++j) dp[conf][j] = inf;

    dp[(1<<0)][0] = 0;//imi fixez nodul de start; acesta fiind 0

    for(int conf=0; conf<(1<<n); ++conf){//iau fiecare configuratie
        for(int j=0; j<n; ++j){//sa ma aflu in fiecare nod;
            if (dp[conf][j] == inf) continue;//daca nu am putut ajunge in aceasta stare;
            if (conf & (1<<j) == 0) continue;//trebuie sa am pe pozita j din conf bit de 1
            //transform fiecare bit de 0 in 1
            //ma aflu in j si vreau sa ma duc in k
            for(int k=0; k<n; ++k){
                if ( (conf & (1<<k) ) == 0 ){//daca am bit de 0; il transform in 1
                    if ( cost[j][k] == 0) continue;//daca nu am muchie de la j la k
                    int new_conf = conf | (1<<k);
                    dp[new_conf][k] = min( dp[new_conf][k], dp[conf][j] + cost[j][k] );
                }
            }
        }
    }

    int ok = 0;//presuspun ca nu exista
    for(int i=1; i<n; ++i) if(dp[(1<<n)-1][i] != inf) ok = 1;
    if (ok == 0){
        g << "Nu exista solutie" << "\n";
        return;
    }else {

        //acum trebuie sa gasesc un nod cu muchie intre el si 0 de cost minim
        int Min = inf;
        for(int i=1; i<n; ++i){
            if (dp[(1<<n)-1][i] != inf && cost[i][0] != 0){//daca am putut ajunge in starea (1<<n)-1 si ultimul nod sa fie i si sa am muchie intre i si 0
                Min = min(Min, dp[(1<<n)-1][i] + cost[i][0]);
            }
        }

        g << Min << "\n";

    }
}

int main(){

    citeste();
    rezolva();

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

    return 0;

}