#include <bits/stdc++.h>

#define MAX_N 18
#define MULT (MAX_N * MAX_N * 1000000)

using namespace std;

int cost[MAX_N][MAX_N], dp[MAX_N][1 << MAX_N];

int main() {
    ifstream cin( "hamilton.in" );
    ofstream cout( "hamilton.out" );

    int n, m, minCost, mask, u, v, c;

    cin >> n >> m;
    for ( u = 0; u < n; u++ ) {
        for ( v = 0; v < n; v++ )
            cost[u][v] = MULT;
    }

    while ( m-- ) {
        cin >> u >> v >> c;
        cost[u][v] = c;
    }
    for ( mask = 1; mask < (1 << n); mask++ ) {
        for ( u = 0; u < n; u++ )
            dp[u][mask] = MULT;
    }
    dp[0][1] = 0;
    for ( mask = 1; mask < (1 << n); mask++ ) {
        for ( v = 0; v < n; v++ ) {
            if ( mask & (1 << v) ) {
                for ( u = 0; u < n; u++ ) {
                    if ( u != v && (mask & (1 << u)) )
                        dp[v][mask] = min( dp[v][mask], dp[u][mask - (1 << v)] + cost[u][v] );
                }
            }
        }
    }

    minCost = MULT;
    for ( u = 0; u < n; u++ )
        minCost = min( minCost, dp[u][(1 << n) - 1] + cost[u][0] );

    cout << minCost;

    return 0;
}