#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
///***********************
const int NMAX = 19, OO = 1e8, MAXSTATE = (1 << NMAX);
int n, m, dp[MAXSTATE][NMAX], cost[NMAX][NMAX];
int hamiltonState, ans = OO;

int main() {
    fin >> n >> m;
    hamiltonState = (1 << n) - 1;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }
    for (int i = 0; i <= hamiltonState; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = OO;
    dp[1][0] = 0;
    for (int state = 0; state <= hamiltonState; state++)
        for (int j = 0; j < n; j++)
            if (dp[state][j] != OO)
                for (int next = 0; next < n; next++)
                    if (!((1 << next) & state) && cost[j][next]) {
                        int newState = state | (1 << next);
                        dp[newState][next] = min(dp[newState][next], dp[state][j] + cost[j][next]);
                    }
    for (int i = 1; i < n; i++)
        if (cost[i][0] && dp[hamiltonState][i] != OO)
            ans = min(ans, dp[hamiltonState][i] + cost[i][0]);
    fout << ans << newline;
    fout.close();
    return 0;
}