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

#define maxn 20
#define inf 10000000

int n, m, blabla ;

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(c, y) ) ;
        cost[x][y] = c ;
    }

    for(int i = 1; i <= n; ++i )
        sort( graf[i].begin(), graf[i].end()) ;
}

void back(int level)
{
    blabla++;
    if( blabla % 10000 == 0) {
        int t = clock() - timp ;
        float tact = ( ( float ) t ) / CLOCKS_PER_SEC ;

        if( 0.7 - 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 ;
    }

    if( level == 1 )
    {
        for(int i = 1; i <= n; ++i )
        {
            sel[i] = true ;
            sol[i] = 1 ;
            back( level + 1 ) ;
            sel[i] = false ;
        }
    }
    else
    {
        for(size_t i = 0; i < graf[ sol[level-1] ].size(); ++i )
        {
            int act = graf[ sol[level-1] ][i].second ;

            if( sel[act] == false )
            {
                int costact = graf[ sol[level-1] ][i].first;

                if( costact == 0 )
                {
                    continue ;
                    break ;
                }

                sel[act] = true ;
                sol[level] = act ;
                sumact += costact ;

                back( level + 1 ) ;

                sel[act] = 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 ;

}