#include <fstream>
#include <iostream>

#define NMAX 20
#define MMAX 262150
#define INF 1e9

using namespace std;

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

int n, m;
int x, y;
int adj[NMAX][NMAX];
int mask, newMask; int last;
int dp[1<<18][NMAX];
int pw, rez;
int i, j, k;

int main()
{
    fin >>n>>m;

    for (i = 1; i <= m; ++i)
    {
        fin >>x>>y;
        fin >>adj[x][y];
    }

    pw = 1<<n;
    for (mask = 0; mask < pw; ++mask)
        for (last = 0; last < n; ++last)
            dp[mask][last] = INF;

    dp[1][0] = 0;
    for (mask = 0; mask < pw; ++mask)
        for (last = 0; last < n; ++last)
            if (mask & (1<<last))
            {
                newMask = mask ^ (1<<last);
                for (k = 0; k < n; ++k)
                {
                    if (!adj[k][last] || !(mask & (1<<k))) continue;
                    dp[mask][last] = min(dp[mask][last], dp[newMask][k] + adj[k][last]);
                }
            }

    rez = INF;
    for (k = 0; k < n; ++k)
        if (adj[k][0])
            rez = min(rez, dp[pw-1][k] + adj[k][0]);

    if (rez == INF) fout <<"Nu exista solutie\n";
    else fout <<rez<<'\n';
    fout.close();
    return 0;
}