#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int dp[20][(1 << 19)];
vector<pair<int, int>> adj[20], inv_adj[20];
signed main()
{
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        adj[x].push_back({y, cost});
        inv_adj[y].push_back({x, cost});
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < (1 << n); j++)
            dp[i][j] = 2 * 1e9;
    }
    dp[0][1] = 0;
    for (int msk = 1; msk < (1 << n); msk++)
    {
        for (int i = 0; i < n; i++)
        {
            if (msk & (1 << i))
            {
                int prev = msk ^ (1 << i);
                if (prev == 0)
                    continue;
                for (auto muchie : inv_adj[i])
                {
                    int nod = muchie.first;
                    int cost = muchie.second;
                    if ((1 << nod) & prev)
                    {
                        dp[i][msk] = min(dp[i][msk], dp[nod][prev] + cost);
                    }
                }
            }
        }
    }
    int full_msk = (1 << n) - 1;
    int mn = 2 * 1e9;
    for (int i = 0; i < n; i++)
    {
        for (auto muchie : adj[i])
        {
            int nod = muchie.first;
            int cost = muchie.second;
            if (nod != 0)
                continue;
            mn = min(mn, dp[i][full_msk] + cost);
        }
    }
    if (mn == 2 * 1e9)
    {
        fout << "Nu exista solutie";
        return 0;
    }
    fout << mn;
}