#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int cost[20][20];
int dp[262200][20];
vector <int> graph[20];

const int inf = static_cast<const int>(1e8);

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);

    fin>>n>>m;
    for ( int i = 1; i <= m; ++i )
    {
        int x, y, c;
        fin>>x>>y>>c;
        graph[x].push_back(y);
        cost[x][y] = c;
    }

    int ans = inf;
    int maxx = (1<<n);

    for ( int i = 2; i < maxx; ++i )
        for ( int j = 0; j < n; ++j )
            dp[i][j] = inf;

    for ( int mask = 0; mask < maxx; ++mask )
        for ( int j = 0; j < n; ++j )
            if ( (1<<j)&mask )
                for ( auto x:graph[j] )
                    if ( (1<<x)&mask ) dp[mask][j] = min(dp[mask][j],
                                                         dp[mask^(1<<j)][x]+cost[j][x]);

    for ( int i = 0; i < n; ++i )
        if ( cost[0][i] ) ans = min(ans, dp[maxx-1][i]+cost[0][i]);

    fout<<ans<<'\n';
}