#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
using namespace std;

const char iname[] = "hamilton.in";
const char oname[] = "hamilton.out";

const int MAX_N = 16;

inline int has_bit(int n, int i) {
    return (n >> i) & 1;
}

int main(void) {
    ifstream in(iname);
    int N, M;

    vector <int> in_adj[MAX_N];
    int cost[MAX_N][MAX_N];
    memset(cost, 0x3f3f3f3f, sizeof cost);

    assert(in >> N >> M);
    assert(1 <= N && N <= 16);
    assert(1 <= M && M <= N*(N-1)/2);
    for (; M > 0; -- M) {
        int x, y, c;
        assert(in >> x >> y >> c);
        assert(0 <= x && x < N);
        assert(0 <= y && y < N);
        assert(1 <= c && c <= 1000000);
        assert(x != y);
        assert(find(in_adj[y].begin(), in_adj[y].end(), x) == in_adj[y].end());
        in_adj[y].push_back(x);
        cost[x][y] = c;
    }
    in.close();

    int i = 0;
    int C[1][1 << MAX_N][MAX_N];
    memset(C, 0x3f3f3f3f, sizeof C);
    C[i][1 << i][i] = 0;
    for (int j = 0; j < 1 << N; ++ j) {
        for (int k = 0; k < N; ++ k) if (has_bit(j, i) && has_bit(j, k)) {
            vector <int>::iterator v;
            for (v = in_adj[k].begin(); v != in_adj[k].end(); ++ v) {
                if (has_bit(j, *v))
                    C[i][j][k] = min(C[i][j][k], C[i][j ^ (1 << k)][*v] + cost[*v][k]);
            }
        }
    }
    int res = 0x3f3f3f3f;
    for (int k = 0; k < N; ++ k)
        res = min(res, C[i][(1 << N) - 1][k] + cost[k][i]);
    ofstream out(oname);
    out << res;
    out.close();
    return 0;
}