#include <bits/stdc++.h>
#define nmax (1 << 18) + 5
#define inf 2e9

using namespace std;

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

int n, m;
int nr;

int dp[nmax][20];
int cost[20][20];

vector <int> g[nmax]; //graful cu sensul invers

inline void read()
{
    fin >> n >> m;
    for (int i = 0; i <= (1 << n); ++i)
        for (int j = 0; j <= n; j++)
            dp[i][j] = inf;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cost[i][j] = inf;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        g[b].push_back(a);
        fin >> cost[a][b];
    }
}

inline void dinamica()
{
    dp[1][0] = 0;
    nr = (1 << n);
    for (int stare = 0; stare < nr; stare++)
    {
        for (int i = 0; i < n; i++)
        {
            if (stare & (1 << i))
            {
                for (int j : g[i])
                {
                        dp[stare][i] = min(dp[stare][i], dp[stare ^ (1 << i)][j] + cost[j][i]);
                }
            }
        }
    }
}

inline void print()
{
    int ans = inf;
    for (int i : g[0])
    {
        ans = min(ans, dp[nr - 1][i] + cost[i][0]);
    }
    if (ans == inf)
        fout << "Nu exista solutie";
    else
        fout << ans;
}

int main()
{
    read();
    dinamica();
    print();
    return 0;
}