#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

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

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

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

int main()
{
    int n, m, x, y, c, mask, i;

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

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

    dp[1][0] = 0;

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

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

    if(rez == inf)
    {
        fout<<"Nu exista solutie";
    }
    else
    {
        fout<<rez;
    }

    fin.close();
    fout.close();
    return 0;
}