#include <iostream>
#include <fstream>
#include <vector>
#define INF 100000000

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

int n, m, x, y, c;
vector<int>graf[25];
int cost[25][25], hamilton[262150][25];

int main()
{
    fin >> n >> m;

    for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) cost[i][j] = INF;

    for(int  i = 1; i <= m; i++){
        fin >> x >> y >> c;
        graf[y].push_back(x);
        cost[x][y] = c;
    }

    for(int i = 0; i < 1<<n; i++)
        for(int j = 0; j < n; j++)
            hamilton[i][j] = INF;

    hamilton[1][0] = 0;


    for(int i = 0; i < 1<<n; i++)
        for(int j = 0; j < n; j++)
            if(i & (1<<j))
                for(vector<int>::iterator it = graf[j].begin(); it < graf[j].end(); it++)
                    if(i & (1<< *it))
                        hamilton[i][j] = min( hamilton[i][j],
                                          hamilton[i ^ (1 << j)][*it] + cost[*it][j]);

    int rez = INF;
    for(vector<int>::iterator it = graf[0].begin(); it < graf[0].end(); it++)
        rez = min(rez, hamilton[(1 <<n) - 1][*it] + cost[*it][0]);

    if(rez == INF)
        fout << "Nu exista solutie" << endl;
    else fout << rez << endl;

    return 0;
}