#include <bits/stdc++.h>
#include <fstream>

using namespace std;

int dp[18][(1 << 18)];
vector<pair<int, int>> G[18];
int n, m;

void ReadInput() {
    ifstream f("hamilton.in");
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back({y, c});
    }
    f.close();
}

int main() {
    ReadInput();
    for (int i = 0; i < n; i++)
        for (int mask = 0; mask < (1 << n); mask++)
            dp[i][mask] = 1e9;
    dp[0][1] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u)))
                continue;
            for (auto it : G[u]) {
                int v = it.first;
                int cost = it.second;
                if (mask & (1 << v))
                    continue;
                dp[v][mask | (1 << v)] = min(dp[v][mask | (1 << v)], dp[u][mask] + cost);
            }
        }
    }
    int ans = 1e9;
    for (int i = 0; i < n; i++)
        for (auto it : G[i]) {
            int v = it.first;
            int cost = it.second;
            if (v == 0)
                ans = min(ans, dp[i][(1 << n) - 1] + cost);
        }
    ofstream g("hamilton.out");
    if (ans == 1e9)
        g << "-1\n";
    else
        g << ans << "\n";
    return 0;
}