#include <bits/stdc++.h>
#define pb push_back

using namespace std;

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

const int MAXN = 20, MAX = (1 << 20), INF = 0x3f3f3f3f;

int dp[MAX][MAXN], cost[MAXN][MAXN], n, m, last;
vector<int> graph[MAXN];

void initialize()
{
    last = (1 << n) - 1;
    for (int i = 0; i <= last; ++i)
        for (int j = 0; j < n; ++j)
            dp[i][j] = INF;
}

void read()
{
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
        graph[y].pb(x);
    }
}

void solve()
{
    dp[1][0] = 0;
    for (int i = 1; i <= last; ++i)
        for (int j = 1; j < n; ++j)
            if (i && (1 << j))
                for (const auto& it: graph[j])
                    dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][it] + cost[it][j]);
}

void print()
{
    int res = INF;
    for (const auto& it: graph[0])
        res = min(res, dp[last][it] + cost[it][0]);
    fout << res << '\n';
}

int main()
{
    read();
    initialize();
    solve();
    print();
    return 0;
}