#include <iostream>
#include <fstream>
#include <vector>

#define inf 1e9
using namespace std;

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

using namespace std;
const int NMAX = 19;
int A[NMAX][NMAX];
vector<int> G[NMAX];
int dp[(1<<NMAX)][NMAX]; // dp[i][j] submultimea din i noduri care se termina in nodul j care formeaza cel mai bun lant hamiltonian

int main()
{
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x,y,c;
        fin >> x >> y >> c;
        G[y].push_back(x);
        A[x][y] = c;
    }

    //linia 0 e nonsense
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = inf;

    dp[1][0] = 0;
    for (int conf = 1; conf < (1 << n); conf++) //pentru fiecare submultime de noduri
        for (int i = 0; i < n; i++) //pentru fiecare nod ce l-am putea selecta
            if (conf & (1<<i))
    {
        int prevconf = conf ^ (1 << i); //o subconfiguratie pentru multimea curenta
        // (se termina in vecinii nodul i)
        for (int j : G[i])
            if (prevconf & (1<< j)) //configuratie precendeta ce se termina in j
                dp[conf][i] = min(dp[conf][i], dp[prevconf][j] + A[j][i]); //update config

    }

    int Sol = inf;
     for(auto i : G[0]) //pentru fiecare lant care se termina intr-un nod ce poate inchide ciclul
        Sol = min(Sol,dp[(1<<n)-1][i] + A[i][0]);
    if(Sol != inf)
        fout << Sol << "\n";
    else
        fout <<"Nu exista solutie\n";

    return 0;
}