#include <fstream>
#include <vector>
#include <cstring>

#define v first
#define c second
#define INF 0x3f3f3f3f

using namespace std;

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

int N, M, MT[18];
int D[18][(1 << 18)];
vector<pair<int, int> > L[18];

int main()
{
    fin >> N >> M;

    memset(D, INF, sizeof(D));
    memset(MT, INF, sizeof(MT));

    for(int i = 1; i <= M; i ++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        L[x].push_back(make_pair(y, cost));
        if(!y)
        {
            MT[x] = cost;
        }
    }


    D[0][1] = 0;

    for(int bitmask = 1; bitmask < (1 << N); bitmask += 2)
    {
        for(int i = 0; i < N; i ++)
        {
            if(D[i][bitmask] != INF)
            {
                for(int j = 0; j < L[i].size(); j ++)
                {
                    int a = L[i][j].v, b = L[i][j].c;
                    if((bitmask & (1 << a)) == 0)
                    {
                        D[a][ bitmask + (1 << a) ] = min(D[a][ bitmask + (1 << a) ], D[i][bitmask] + b);
                    }
                }
            }
        }
    }

    int solution = INF;

    for(int i = 1; i < N; i ++)
    {
        if(MT[i] != INF && D[i][ ((1 << N) - 1) ] != INF)
        {
            solution = min(solution, D[i][ ((1 << N) - 1) ] + MT[i]);
        }
    }

    if(solution == INF)
    {
        fout << "Nu exista solutie";
        return 0;
    }

    fout << solution;



    return 0;
}