#include <bits/stdc++.h>
#define infinit 1000000000

using namespace std;

vector <int> h[22];
int n;
int best[22][262150], mat[22][22];
/// best[i,j]=costul minim al unui drum de la nodul 0 la nodul i,
///    trecand prin "starea" j (18 valori binare)

void Citire()
{
    int i, x, y, cost, m;
    ifstream fin("hamilton.in");
    fin >> n >> m;
    for (x = 0; x < n; x++)
        for (y = 0; y < n; y++)
            mat[x][y] = infinit;
    for (i = 1; i <= m; ++i)
    {
        fin >> x >> y >> cost;
        mat[x][y] = cost;
        h[x].push_back(y);
    }
    fin.close();
}

void Rezolva()
{
    queue < pair<int,int> > q;
    int i, k, stare, stare1, cost, X;
    unsigned int j;
    X = (1 << n) - 1;
    for (i = 0; i < n; i++)
        for (j = 0; j <= X; j++)
            best[i][j] = infinit;
    best[0][1] = 0;
    q.push(make_pair(0, 1));
    while (!q.empty())
    {
        k = q.front().first;
        stare = q.front().second;
        q.pop();
        for (j = 0; j < h[k].size(); j++)
        {
            i = h[k][j]; /// arcul (k,i)
            cost = mat[k][i];
            if ((stare & (1 << i)) == 0) /// n-am mai trecut prin nodul i
            {
                stare1 = (stare | (1 << i));
                if (best[i][stare1] > best[k][stare] + cost)
                {
                    best[i][stare1] = best[k][stare] + cost;
                    q.push(make_pair(i, stare1));
                }
            }
        }
    }
    cost = infinit;
    for (i = 1; i < n; i++)
        cost = min(cost, best[i][X] + mat[i][0]);
    ofstream fout("hamilton.out");
    if (cost == infinit) fout << "Nu exista solutie\n";
    else fout << cost << "\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolva();
    return 0;
}