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

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int NMAX = 20;

int n, m;
long long cost[NMAX][NMAX];
long long dp[NMAX][(1 << 18) + 4];
vector<pair<pair<int, int>, int>> edges;
long long rez = INT_MAX;

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        edges.push_back({{a, b}, c});
        cost[a][b] = c;
    }
    for (int conf = 0; conf < (1 << n); conf++)
    {
        for (int i = 0; i < n; i++)
        {
            dp[i][conf] = INT_MAX;
        }
    }
    dp[0][1] = 0;
    for (int conf = 1; conf < (1 << n); conf++)
    {
        for (auto edge : edges)
        {
            int i = edge.first.first;
            int j = edge.first.second;
            int c = edge.second;
            if ((conf & (1 << i)) && (conf & (1 << j)))
            {
                dp[j][conf] = min(dp[j][conf], dp[i][conf ^ (1 << j)] + c);
            }
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (cost[i][0] != 0)
        {
            rez = min(rez, dp[i][(1 << n) - 1] + cost[i][0]);
        }
    }
    if (rez == INT_MAX)
    {
        rez = -1;
    }
    fout << rez;
    return 0;
}