#include <bits/stdc++.h>
#define in "hamilton.in"
#define out "hamilton.out"
using namespace std;
ifstream fin(in);
ofstream fout(out);

int n,m;
vector <pair <int,int> > L[20];
int dp[18][ (1<<18) + 3];
queue <pair <int,int> > q;

void Citire()
{
    int i,x,y,c;

    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back({y,c});
    }
}

int Cost(int nod)
{
    int i,j;

    for (auto w : L[nod])
    {
        i = w.first; /// nod adiacent
        j = w.second; /// cost

        if (i == 0) return j;
    }
    return 1000000000;
}

void Dyn()
{
    int i,j;
    int nod,mask,x;

    q.push({0,1});
    while(!q.empty())
    {
        nod = q.front().first;
        mask = q.front().second;
        q.pop();

        for (auto k : L[nod])
        {
            i = k.first; /// nodul adiacent
            j = k.second; /// costul muchiei (nod,i)

            if ((mask & (1 << i)) == 0)
            {
                x = mask | (1<<i) ;
                if (dp[i][x] == 0) dp[i][x] = dp[nod][mask] + j;
                else dp[i][x] = min (dp[i][x], dp[nod][mask] + j);

                q.push({i,x});
            }
        }
    }

    int N = (1 << n) - 1;

    x = 1000000000;
    for (nod = 1; nod <= n-1; nod++)
        if (dp[nod][N] != 0) x = min(x, Cost(nod) + dp[nod][N]);

    if (x != 1000000000) fout << x << "\n";
    else fout << "Nu exista solutie\n";
}

int main()
{
    Citire();
    Dyn();

    fin.close();
    fout.close();
    return 0;
}