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

const int N = 18, inf = 0x3f3f3f3f;

struct Edge{
    int y, c;
    Edge(int y, int c) : y(y), c(c) {};
};

int best[1 << N][N], n;
vector<Edge> graph[N];

void printCheck(){
    for (int i = 0 ; i < (1 << n) ; i++){
        for (int j = 0 ; j < n ; j++)
            cout << best[i][j] << "\t";
        cout << '\n';
    }
}

int main(){
    ifstream in("hamilton.in");
    int m, x, y, c;

    in >> n >> m;
    while (m--){
        in >> x >> y >> c;
        graph[y].push_back( Edge(x, c) );
    }
    in.close();

    memset(best, inf, sizeof(best));
    best[0][0] = 0;

    for (int i = 1 ; i < (1 << n) ; i++)
        for (int j = 0 ; j < n ; j++)
            if ( i & (1 << j) )
                for (Edge E : graph[j])
                    best[i][j] = min(best[i][j], E.c + best[i ^ (1 << j)][E.y]);

    ofstream out("hamilton.out");
    if ( best[ (1 << n) - 1 ][0] != inf )
        out << best[ (1 << n) - 1 ][0] << '\n';
    else
        out << "Nu exista solutie\n";
    out.close();

    return 0;
}