#include <bits/stdc++.h>
#define n 18
using namespace std;

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

inline void min_self(int& a, int b) {
    a = min(a, b);
}

vector <int> G[n];
int cost[n][n], dp[1 << n][n];
int main() {
    int N, M;
    fin >> N >> M;

    memset(cost, 0x3f, sizeof cost);
    memset(dp, 0x3f, sizeof dp);

    while(M--) {
        int u, v;
        fin >> u >> v >> cost[u][v];
        G[v].emplace_back(u);
    }
    dp[1][0] = 0;
    for(int mask = 1; mask < (1 << N); ++mask)
        for(int node = 0; node < N; ++node)
            if(mask & (1 << node))
                for(int vec : G[node])
                    if(mask & (1 << vec))
                        min_self(dp[mask][node], dp[mask ^ (1 << node)][vec] + cost[vec][node]);
    int ans(__builtin_inf());
    for(int node : G[0])
        min_self(ans, dp[(1 << N) - 1][node] + cost[node][0]);
    fout << ans;
}