/// dp[mask][i] - costul minim cu care ajung in nodul i trecand prin nodurile din mask
/// dp[mask][i] = min(dp[mask][i], dp[mask - (1<<i)][j] + c)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int inf = (1<<29);
const int NMAX = 18;

int dp[1<<NMAX][NMAX];

vector<pair<int, int> > v[NMAX];

int main()
{
    int n, m, i, j, x, y, c;
    fin>>n>>m;

    for(i=0; i<m; i++)
    {
        fin>>x>>y>>c;
        v[y].push_back({x, c});
    }

    for(i=0; i<(1<<n); i++)
    {
        for(j=0; j<n; j++)
        {
            dp[i][j] = inf;
        }
    }

    dp[1][0] = 0;

    int k;
    for(k=0; k<(1<<n); k++)
    {
        for(i=1; i<n; i++)
        {
            if((1<<i) & k)
            {
                for(auto el : v[i])
                {
                    j = el.first;
                    c = el.second;
                    dp[k][i] = min(dp[k][i], dp[k - (1<<i)][j] + c);
                }
            }
        }
    }

    ///inchid ciclul
    int rez = inf;
    for(auto el : v[0])
    {
        j = el.first;
        c = el.second;
        rez = min(rez, dp[(1<<n) - 1][j] + c);
    }

    if(k == inf)
        fout<<"Nu exista solutie";
    else
        fout<<rez;
    fin.close();
    fout.close();
    return 0;
}