#include <fstream>
#include <list>
#define INF 1999999999
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

list<int> transposeGraph[20];
int matCost[20][20], dynamicProg[1 << 19][20];
int n, m, x, y, c, i, j, solution;

int main()
{
    fin>>n>>m;
    for (i = 0 ; i < n ; i++)
        for (j = 0 ; j < n ; j++)
            matCost[i][j] = INF;

    for (i = 1 ; i <= ( 1 << n ) - 1 ; i++)
        for (j = 0 ; j <= n ; j++ )
            dynamicProg[i][j] = INF;

    for (i = 1 ; i <= m ; i++) {
        fin>>x>>y>>c;

        matCost[x][y] = c;
        transposeGraph[y].push_back(x);
    }

    dynamicProg[1][0] = 0;
    for (i = 1 ; i <= ( 1 << n ) - 1 ; i++) {
        for (j = 0 ; j < n ; j++) {
            if ( ( 1 << j ) & i ) {
                for (list<int>::iterator it = transposeGraph[j].begin() ; it != transposeGraph[j].end() ; it++) {
                    if ( ( 1 << *it ) & i ) {
                        dynamicProg[i][j] = min( dynamicProg[i][j] , dynamicProg[i ^ (1 << j)][*it] + matCost[*it][j]);
                    }
                }
            }
        }
    }

    solution = INF;
    for (list<int>::iterator it = transposeGraph[0].begin() ; it != transposeGraph[0].end() ; it++) {
        solution = min(solution, dynamicProg[ ( 1 << n ) - 1 ][*it] + matCost[*it][0]);
    }

    if (solution == INF) {
        fout<<"Nu exista solutie";
    } else {
        fout<<solution;
    }

    return 0;
}