#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define newn a[nod][i]

using namespace std;

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

const int N = 19;
const int oo = 0x3f3f3f3f;
const int MAXC = (1 << 18) + 100;

int n, m, sol, c[MAXC][N], cst[N][N];
vector <int> a[N];

int Comp(int conf, int nod)
{
    if(c[conf][nod] < 0)
    {
        c[conf][nod] = oo;
        for(size_t i=0; i<a[nod].size(); i++)
            if(conf & (1<<newn))
            {
                if(!newn && conf != (1<<(nod)) + 1) continue;
                c[conf][nod] = min(c[conf][nod], Comp(conf ^ (1<<nod), newn) + cst[nod][newn]);
            }
    }
    return c[conf][nod];
}

int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x, y;
        fin>>x>>y;
        a[y].push_back(x);
        fin>>cst[y][x];
    }

    memset(c, -1, sizeof c);
    c[1][0] = 0; sol = oo;

    for(size_t i=0; i<a[0].size(); i++)
        sol = min(sol, Comp((1<<n)-1, a[0][i]) + cst[0][a[0][i]]);

    if(sol != oo) fout<<sol;
    else fout<<"Nu exista solutie";
    return 0;
}