#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#define N 18
#define INF 1e9

using namespace std;

vector < pair< int, int > > muc [ N ] ;
vector < pair< int, int > >::iterator it  ;

int dp [ 1<< ( N + 1 ) ][ N ];
int d [ N ];

void printmat ( int n ){
    static int i , j ;

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

        for ( j = 0 ; j < n ; j ++  ){
            printf("%15d ",dp[ i ][ j ] );
        }
        printf("\n");
    }

}

int main(){
    int n , m ;
    int i , j ;
    int x , y , cost ;

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

    scanf("%d%d",&n,&m);

    for ( i = 0 ; i < n ;i++ ){
        d [ i ] = INF ;
    }

    for ( i = 0 ; i < m ; i++ ){
        scanf("%d%d%d", &x , &y , &cost );
        muc [ x  ].push_back ( make_pair( y , cost ) );

        if ( y == 0 ){
            d [ x ] = min ( d [ x ], cost );
        }

    }

    for ( i = 0 ; i < ( 1 << n ) ; i++ ){
        for ( j = 0 ; j < n ; j ++ ){
            dp [ i ][ j ]= INF ;
        }
    }


    for ( it = muc [ 0 ].begin() ; it != muc [ 0 ].end() ; it++ ){

        x = it->first ;

        dp [  ( 1<< x ) ][ x ] =  it->second  ;

    }


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

        for ( j = 1 ; j < n ; j ++  ){

            if ( dp [ i ][ j ] ==INF ){
                continue ;
            }

            for ( it = muc [ j ].begin() ; it != muc [ j ].end() ; it++ ){

                x = it->first ;

                if (  i & ( 1 << x ) ){
                    continue ;
                }

                dp [ i + ( 1<< x ) ][ x ] = min ( dp [ i + ( 1<< x ) ][ x ] , dp [ i ][ j ] + it->second  );


            }

        }


    }



    printf("%d", dp [ (1 << n) - 1][ 0 ] );

    //printmat( n );

    return 0;
}