#include <iostream>

#include <fstream>

#include <cstring>

#include <algorithm>

#include <vector>





using namespace std;

ifstream f ("hamilton.in");

ofstream g ("hamilton.out");

#define Gmax 18

vector < int > G[Gmax];
int c[1 << Gmax][Gmax]; /// c[i][j] = costul minim al unui drum care trece prin toate nodurile din multimea i si se termina in j
int d[Gmax][Gmax];

int main()
{
    memset(c, 0x3f, sizeof(c));
    memset(d, 0x3f, sizeof(d));

    int n, m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x, y, z;
        f>>x>>y>>z;
        G[y].push_back(x);
        d[x][y] = z;
    }
    c[1][0] = 0;
    for(int i=1; i < (1 << n); i++)
        for(int j=0;j < n; j++)
        {
             if(i & (1 << j) == 0)
                continue;
            for(auto it = G[j].begin();it!= G[j].end(); it++)
            {
                if(i & (1<<*it) == 0)
                    continue;
                c[i][j] = min(c[i][j], c[i ^ (1<<j)][*it] + d[*it][j]);

            }


        }

    int sol = 0x3f3f3f3f;
    for(auto it = G[0].begin(); it!= G[0].end(); ++it)
    {
        sol = min(sol, c[(1<<n)-1][*it] +  d[*it][0]);
    }
    if(sol == 0x3f3f3f3f)
        g << "Nu exista solutie" << endl;
    else g << sol;
    return 0;
}