#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

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

const int NMAX = 18, DIM = (1 << 18);
int cost[NMAX + 1][NMAX + 1], dp[DIM + 1][NMAX + 1];
vector < int > G[NMAX + 1];

int main() {
    int N, M;
    fin >> N >> M;
    for(int i = 0; i < NMAX; ++i)
        for(int j = 0; j < NMAX; ++j)
            cost[i][j] = INF;
    while(M--) {
        int u, v;
        fin >> u >> v >> cost[u][v];
        G[v].emplace_back(u);
    }
    for(int i = 0; i < DIM; ++i)
        for(int j = 0; j < NMAX; ++j)
            dp[i][j] = INF;
    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 = INF;
    for(int node : G[0])
        min_self(ans, dp[(1 << N) - 1][node] + cost[node][0]);
    fout << ans;
}