#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

#define inf 0x3f3f3f3f
#define GMAX 18

vector <int> G[GMAX];
int c[1<<GMAX][GMAX];
int d[GMAX][GMAX];
//int mat[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 = inf;
    for(auto it = G[0].begin();it!=G[0].end();it++)
    {
        Sol = min(Sol, c[(1<<n)-1][*it] + d[*it][0]);
    }

    #define cout g
    if(Sol == inf)
        cout<<"Nu exista solutie";
    else
    cout<<Sol;
    return 0;
}