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

#define NMAX 19
#define MMAX 263000
#define INFI 0x3f3f3f3f

vector < int > g[ NMAX ];

int    v[ MMAX ][ NMAX ],
    cost[ NMAX ][ NMAX ];

int compute( int reprezentareBinara, int nod ){

    vector < int > :: iterator it;

    if( v[ reprezentareBinara ][ nod ] == -1 ){   /// necalculat inca
        v[ reprezentareBinara ][ nod ] = INFI;
        for( it = g[ nod ].begin(); it != g[ nod ].end(); ++it ){
            if( reprezentareBinara & ( 1 << ( *it ) )  ){ /// daca apartine sir
                if( *it == 0 && reprezentareBinara != ( 1 << nod ) + 1 ) continue ; /// daca umeaza nodul de start si este ultimul de adaugat
                v[ reprezentareBinara ][ nod ] = min( v[ reprezentareBinara ][ nod ], compute( reprezentareBinara ^ ( 1 << nod ), *it ) + cost[ *it ][ nod ]  ); /// eliminam nod curent, si calculam pentru vecini
            }
        }
    }

    return v[ reprezentareBinara ][ nod ];

}

int main()
{

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

    int n, m, i, j, x, y, sol;

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

    for( i = 0; i < n; ++i )
        for( j = 0; j < n; ++j ) cost[ i ][ j ] = INFI;

    while( m-- ){
        scanf("%d%d",&x,&y);
        scanf("%d",&cost[ x ][ y ]);
        g[ y ].push_back( x );
    }

   memset( v, -1, sizeof( v ));

    sol = INFI;
    v[ 1 ][ 0 ] = 0;
    for( i = 0; i < g[ 0 ].size(); ++i )
        sol = min( sol, compute( ( 1 << n ) - 1, g[ 0 ][ i ] ) + cost[ g[ 0 ][ i ] ][ 0 ] );

    if( sol != INFI ) printf("%d\n",sol);
    else printf("-1");

    return 0;
}