#include <fstream>

using namespace std;

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

int n, m;

int ans, adj[20][20];
bool vis[20];

void bkt ( int l, int prev, int cost ) {

    if ( cost > ans )
        return;

    if ( l >= n ) {
        if ( adj[prev][0] )
            ans = min ( ans, cost + adj[prev][0] );
        return;
    }

    for ( int i = 1; i < n; i++ ) {

        if ( !vis[i] && adj[ prev ][ i ] ) {

            vis[i] = true;
            bkt ( l+1, i, cost + adj[prev][i] );
            vis[i] = false;
        }
    }
}

void solve () {

    ans = 18000005;
    bkt ( 1, 0, 0 );
    fout << ans << "\n";
}

void read () {

    fin >> n >> m;

    int from, to, cost;
    for ( int i = 1; i <= m; i++ ) {

        fin >> from >> to >> cost;
        adj[ from ][ to ] = cost;
        //adj[ to ][ from ] = cost;
    }
}

int main()
{
    read ();
    solve ();
    return 0;
}