#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 18, MAXSTATE = 1<<19, INF = 1<<19;
int dp[MAXN][MAXSTATE], cost[MAXN][MAXN], N, M;

void readData()
{
    scanf("%d %d",&N,&M);

    for(int i = 1; i <= M; i++)
    {
        int a, b, c; scanf("%d %d %d",&a,&b,&c);
        cost[ a ][ b ] = c;
    }
}

void initWithINF(int mat[MAXN][MAXN])
{
    for(int i = 0; i < MAXN; i++)
        for(int j = 0; j < MAXN; j++)
            mat[ i ][ j ] = INF;
}

int f(int node, int state)
{
    if( dp[ node ][ state ] != 0 )
        return dp[ node ][ state ];
    else
    {
        dp[ node ][ state ] = INF;

        for(int i = 1; (state>>i); i++)
            if( (state>>i) % 2 == 1 && cost[ node ][ i ] != INF )
            {
                int aux = f(i,state^(1<<i));
                dp[ node ][ state ] = min( dp[ node ][ state ], cost[ node ][ i ] + aux );
            }

        return dp[ node ][ state ];

        int deProba = 0;
    }
}



int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);

    initWithINF(cost);
    readData();

    dp[ 0 ][ 0 ] = INF;

    for(int i = 1; i < N; i++)
        dp[ i ][ 0 ] = cost[ i ][ 0 ];

    cout<<f( 0, (1<<N) - 2);

    return 0;
}