#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int NMax = 18;
const int oo = 1e9;
int A[NMax + 5][NMax + 5];
vector <int> G[NMax + 5];
int DP[(1<<18) + 5][NMax + 5];
int N,M;
int main()
{
    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;
    }

    for(int i = 0; i < (1<<N); ++i)
        for(int j = 0; j < N; ++j)
            DP[i][j] = oo;
    DP[1][0] = 0;
    for(int Conf = 1; Conf < (1<<N); ++Conf)
    {
        for(int i = 0; i < N; ++i)
        {
            if(Conf & (1<<i))
            {
                int OldConf = Conf ^ (1<<i);
                for(auto j : G[i])
                    if(OldConf & (1<<j))
                    DP[Conf][i] = min(DP[Conf][i],DP[OldConf][j] + A[j][i]);
            }
        }
    }
    int Sol = oo;
    for(auto i : G[0])
        Sol = min(Sol,DP[(1<<N)-1][i] + A[i][0]);
    if(Sol != oo)
        fout << Sol << "\n";
    else
        fout <<"Nu exista solutie\n";
    return 0;
}