#include <bits/stdc++.h>

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int n, m, x, y, cost;
int c[20][20];
int d[20][(1 << 18) + 10];
vector<int> adj[20];

int main()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> cost;
        c[x][y] = cost;
        adj[y].push_back(x);
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < (1 << n); j++)
            d[i][j] = 1e9;

    d[0][1] = 0;

    for (int j = 0; j < (1 << n); j++)
        for (int i = 0; i < n; i++)
            if (j & (1 << i)) {
                for (auto it : adj[i]) {
                    if (j & (1 << it)) {
                        d[i][j] = min(d[i][j], d[it][j ^ (1 << i)] + c[it][i]);
                    }
                }
            }

    int ans = 1e9;
    for (auto it : adj[0])
        ans = min(ans, d[it][(1 << n) - 1] + c[it][0]);
    out << ans << '\n';
    return 0;
}