#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#define NMAX 20
#define INF 1e9

using namespace std;

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

int nodes, edges;
int adj[NMAX][NMAX], dp[1<<18+5][NMAX];
vector <int> graph[NMAX];

void init (){
    for (int i=0; i<nodes; ++i)
        for (int j=0; j<nodes; ++j)
            adj[i][j] = INF;

    for (int i=0; i< 1<<nodes; ++i)
        for (int j=0; j<nodes; ++j)
            dp[i][j] = INF;
}

int main (){
    int x, y, cost;

    in >> nodes >> edges;
    init();

    for (int i=1; i<=edges; ++i){
        in >> x >> y >> cost;

        graph[y].push_back(x);
        adj[x][y] = cost;
    }

    dp[1][0] = 0;
    for (int i=0; i < 1<<nodes; ++i){
        for (int j=0; j < nodes; ++j){
            if (i & (1<<j)){
                for (auto k:graph[j]){
                    if (i & (1<<k))
                        dp[i][j] = min(dp[i][j], dp[i^(1<<j)][k] + adj[k][j]);
                }
            }
        }
    }

    int res = INF;
    for (auto k:graph[0])
        res = min(res, dp[(1<<nodes)-1][k] + adj[k][0]);
     
    if (res == INF)
        out << "Nu exista solutie";
    else out << res;

    return 0;
}