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

#define maxn 20
#define inf 10000000

int n, m ;

vector< pair<int, int> > graf[maxn] ;

int cost[maxn][maxn] ;

int sumact, mins = inf ;

int sol[maxn] ;
bool sel[maxn] ;

clock_t timp ;

void citire()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; ++i )
    {
        int x, y, c ;

        scanf("%d%d%d", &x, &y, &c);

        ++x ;
        ++y ;

        graf[x].push_back( make_pair(y, c) ) ;
        cost[x][y] = c ;
    }
}

void back(int level)
{
    int t = clock() - timp ;
    float tact = ( ( float ) t ) / CLOCKS_PER_SEC ;

    if( 0.75 - tact < 0.001 )
    {
        printf("%d\n", mins);
        exit(0) ;
    }

    if( level == n + 1 )
    {
        int costact = cost[ sol[n] ][ sol[1] ] ;

        if( costact > 0 )
        {
            sumact += costact ;
            mins = min( sumact, mins ) ;
            sumact -= costact;
        }

        return ;
    }

    for(int i = 1; i <= n; ++i)
    {
        if( sel[i] == false && sumact < mins )
        {

            int costact = cost[ sol[level-1] ][ i ] ;

            if( costact == 0 && level != 1 )
                continue ;


            sel[i] = true ;
            sol[level] = i ;

            sumact += costact ;

            back( level + 1 ) ;

            sel[i] = false ;
            sumact -= costact ;
        }
    }
}

int main()
{
    timp = clock() ;

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

    citire() ;

    back(1) ;

    if( mins == inf )
        puts("Nu exista solutie") ;

    if( mins < inf )
        printf("%d\n", mins);

    timp = clock() - timp ;

    return 0 ;

}