#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);
}

int cost[18][18], dp[1 << 18][18];
int main() {
    memset(cost, 0x3f, sizeof cost);
    memset(dp, 0x3f, sizeof dp);

    int N, M;
    fin >> N >> M;
    
    while(M--) {
        int u, v;
        fin >> u >> v;
        fin >> cost[u][v];
    }
    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 = 0; vec < N; ++vec)
                    if(mask & (1 << vec))
                        min_self(dp[mask][node], dp[mask ^ (1 << node)][vec] + cost[vec][node]);
    int ans = INF;
    for(int vec = 0; vec < N; ++vec)
        min_self(ans, dp[(1 << N) - 1][vec] + cost[vec][0]);
    fout << ans;
}