#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;

#define nod first
#define cost second

vector<pair<int, int> >graf[20];
int dp[10005][25];

int n;

void dfs(int nod, int colect){
    if(colect == (1 << n) - 1) return;
    for(auto x : graf[nod]){
        if(colect & (1 << x.first)) continue;
        dp[colect | (1 << x.first)][x.first] = min(dp[colect | (1 << x.first)][x.first], dp[colect][nod] + x.second);
        dfs(x.first, colect | (1 << x.first));
    }
}

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    int m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        graf[x].push_back({y, c});
    }
    for(int i = 1; i < (1 << n); ++i){
        for(int j = 0; j < n; ++j)
            dp[i][j] = 1 << 30;
    }
    dfs(0, 0);
    int ans = 1 << 30;
    for(int i = 0; i < n; ++i) ans = min(ans, dp[(1 << n) - 1][i]);
    fout << ans;
    return 0;
}