#include <bits/stdc++.h>

using namespace std;

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

const int maxNodes = 20;
const int maxBits = (1<<18)+5;
const int infinite = 1e9;

int totalNodes, totalEdges, solution;

int cost[maxNodes][maxNodes],
    dynamic[maxBits][maxNodes];

vector <int> edges[maxNodes];

inline void readVariables(){
    fin >> totalNodes >> totalEdges;

    for ( int indexOrigin = 0; indexOrigin < totalNodes; indexOrigin++ )
        for ( int indexDestination = 0; indexDestination < totalNodes; indexDestination++ )
            cost[indexOrigin][indexDestination] = infinite;

    int origin, destination;
    for ( ; totalEdges; totalEdges-- ){
        fin >> origin >> destination;
        edges[origin].push_back(destination);
        fin >> cost[destination][origin];
    }
}

int main(){
    readVariables();

    for ( int indexBits = 0; indexBits < (1<<totalNodes); indexBits++ )
        for ( int indexNode = 0; indexNode < totalNodes; indexNode++ )
            dynamic[indexBits][indexNode] = infinite;

    for ( int indexNode = 0; indexNode < totalNodes; indexNode++ )
        dynamic[1<<indexNode][indexNode] = 0;

    for ( int indexBits = 0; indexBits < (1<<totalNodes); indexBits++ )
        for ( int indexNode = 0; indexNode < totalNodes; indexNode++ )
            if ( indexBits & (1<<indexNode) )
                for ( auto it : edges[indexNode] )
                    if ( indexBits & (1<<it) )
                        dynamic[indexBits][indexNode] = min (dynamic[indexBits][indexNode], dynamic[indexBits^(1<<indexNode)][it] + cost[it][indexNode]);

    solution = infinite;
    for ( auto it : edges[0] )
        solution = min (solution, dynamic[(1<<totalNodes)-1][it] + cost[it][0]);
    if ( solution == infinite )
        fout << "Nu exista solutie";
    else
        fout << solution;
    return 0;
}