#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

// nodes are indexed from 0 !!!
// INF on cost when invalid edges
int hamiltonian_cycle_with_minimum_cost(int n, vector<vector<int>> graph, vector<vector<int>> cost) {
    int const M = 1 << n, INF = 1e9;
    vector<vector<int>> min_cost(n, vector<int>(M, INF));
    min_cost[0][1] = 0;

    for (int mask = 0; mask < M; ++mask) {
        for (int i = 0; i < n; ++i) {
            if (!(mask & (1 << i))) {
                continue;
            }
            for (int dest : graph[i]) {
                if (mask & (1 << dest)) {
                    continue;
                }
                int new_mask = mask | (1 << dest);
                min_cost[dest][new_mask] = min(min_cost[dest][new_mask], min_cost[i][mask] + cost[i][dest]);
            }
        }
    }

    int min_cost_all = min_cost[0][M - 1];
    for (int last : graph[0]) {
        min_cost_all = min(min_cost[last][M - 1] + cost[last][0], min_cost_all);
    }

    return min_cost_all;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int const INF = 1e9;
    int n, m;
    fin >> n >> m;
    vector<vector<int>> graph(n), cost(n, vector<int>(n, INF));
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        graph[a].push_back(b);
        cost[a][b] = c;
    }
    fout << hamiltonian_cycle_with_minimum_cost(n, graph, cost) << '\n';
    return 0;
}