#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

const int Inf = 0x3f3f3f3f;
using VI = vector<int>;
const int MAXN = 18;
vector<vector<pair<int, int>>> G, Gr;
int D[1<<MAXN][MAXN];
int N, M;

void ReadGraph();
void Hamilton();

int main()
{
    ReadGraph();
    Hamilton();

    fin.close();
    fout.close();
    return 0;
}

void ReadGraph()
{
    fin >> N >> M;
    Gr = G = vector<vector<pair<int, int>>>(N + 1);
    int x, y, c;
    while ( M-- )
    {
        fin >> x >> y >> c;
        G[x].push_back({y, c});
        Gr[y].push_back({x, c});
    }
}

void Hamilton()
{
    memset(D, Inf, sizeof(D));
    D[1][0] = 0;
    int i, j, r{Inf};
    for ( i = 2; i < ( 1 << N ); ++i )
        for ( j = 0; j < N; ++j )
            if ( i & ( 1 << j ) )
            {
                for ( const auto& vj : Gr[j] )
                    if ( i & ( 1 << vj.first ) )
                        D[i][j] = min( D[i][j], D[i ^ (1 << j)][vj.first] + vj.second );
            }

    i = ( 1 << N ) - 1;
    for ( j = 0; j < N; ++j )
    {
        int c1 = D[i][j], c2{Inf};
        for ( const auto& x : G[j] )
            if ( x.first == 0 )
            {
                c2 = x.second;
                break;
            }
        r = min( r, c1 + c2 );
    }

    fout << r << '\n';
}