#include <bits/stdc++.h>
using namespace std;

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

int n, m, N, a[21][21], dp[22][(1 << 18) + 2];
// dp[i][j] = costul minim al drumului de la 0...i cu configuratia 

void Citire()
{
    int i, x, y, c;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        a[x][y] = c;
    }
}

void Hamilton()
{
    int i, j, mask, new_mask, minn;
    N = (1 << n);
    for (i = 0; i < n; i++)
        for (mask = 0; mask < N; mask++)
            dp[i][mask] = 2e9;
    //
    dp[0][1] = 0; // ajungem in nodul 1 cu configuratia 00...0001
    for (mask = 3; mask < N; mask += 2)
    {
        for (i = 1; i < n; i++)
        {
            if (mask & (1 << i)) // masca contine nodul i
            {
                new_mask = mask ^ (1 << i); // eliminam bit-ul i din masca
                for (j = 0; j < n; j++)
                {
                    if (a[j][i] != 0 && (new_mask & (1 << j))) // noua masca contine nodul j si muchia exista
                        dp[i][mask] = min(dp[i][mask], dp[j][new_mask] + a[j][i]);
                }
            }
        }
    }
    minn = 2e9;
    for (i = 1; i < n; i++)
        if (a[i][0] != 0 && minn > dp[i][N - 1] + a[i][0]) // nodul 0 a fost lasat liber pentru asigurarea unui bit pentru stergere
            minn = dp[i][N - 1] + a[i][0];
    if (minn == 2e9) fout << "Nu exista solutie\n";
    else fout << minn << '\n';
}

int main()
{
    Citire();
    Hamilton();
    fin.close();
    fout.close();
    return 0;
}