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

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

int n, m;

vector <pair <int, int>> g[25];

int dp[(1 << 19)][30];

const int INF = 1e9;

int kost(int nod1, int nod2)
{
    int ret = 0;
    for(auto it:g[nod1])
    {
        if(it.first == nod2)
            ret = it.second;
    }
    return ret;
}

signed main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, w;
        in >> x >> y >> w;
        g[y].push_back({x, w});
    }
    for(int i = 0; i < (1 << n); i++)
    {
        for(int j = 0; j < n; j++)
        {
            dp[i][j] = 1e9;
        }
    }
    dp[1][0] = 0;
    for(int mask = 3; mask < (1 << n); mask += 2)
    {
        for(int i = 1; i < n; i++)
        {
            if(mask & (1 << i))
                for(auto it:g[i])
                {
                    dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][it.first] + it.second);
                }
        }
    }
    int cost_minim = INF;
    for(int i = 1; i < n; i++)
    {
        cost_minim = min(cost_minim, dp[(1 << n) - 1][i] + kost(i, 0));
    }
    if(cost_minim == INF)
        out << "Nu exista solutie";
    else
        out << cost_minim + 1;
    return 0;
}