#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 ;
    }

    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;

            sel[act] = true ;
            sol[level] = act ;
            sumact += costact ;
            if( sumact < mins)
                back( level + 1 ) ;

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

}

int main()
{
    timp = clock() ;

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

    citire() ;

    sel[1] = 1;
    sol[1] = 1;
    back(2) ;

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

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

    timp = clock() - timp ;

    return 0 ;

}