#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 19;
const int inf = 1e9;
const int Nmax = (1<<18) + 1;
int n,m;
int cost[nmax][nmax];
int d[Nmax][nmax];

int main()
{
    fin>>n>>m;
    int N = (1<<n);
    for(int i=0; i<m; i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        cost[a][b] = c;
    }
    for(int mask = 0; mask < N; mask ++)
        for(int j = 0; j < n; j++)
            d[mask][j] = inf;
    d[1][0] = 0;
    for(int mask = 3; mask < N; mask +=2)
    {
        for(int j = 0; j < n; j++)
        {
            if((1<<j) & mask)
            {
                int prev_mask = mask ^ (1<<j);
                for(int k = 0; k < n; k++)
                {
                    if(((1<<k) & mask) && k!=j && cost[k][j])
                    {
                        d[mask][j] = min(d[mask][j], d[prev_mask][k] + cost[k][j]);
                    }
                }
            }
        }
    }
    int sol = inf;
    for(int i=1; i<n; i++)
        if(cost[i][0])
            sol = min(sol, d[N-1][i] + cost[i][0]);

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