#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in") ;
ofstream fout("hamilton.out") ;

vector<int> graf[20];
int dp[1<<20][20] ;
int cost[20][20] ;
int n , m ;

void citire()
{
    int i , x , y , c ;
    fin >> n >> m ;
    for ( i = 0 ; i < n ; i++ )
        for ( int j = 0 ; j < n ; j++ )
            cost[i][j] = 0x3f3f3f3f ;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> c ;
        graf[x].push_back(y) ;
        cost[x][y] = c;
    }
}

void ciclu()
{
    int i , j , k , vecin ;
    for ( i = 1 ; i <= (1<<n)-1 ; i++ )
        for ( j = 0 ; j < n ; j++ )
            dp[i][j] = 0x3f3f3f3f ;
    for  ( i = 0 ; i <= n ; i++ )
        dp[1<<i][i] = 0 ;
    for ( i = 1 ; i <= (1<<n)-1 ; i++ )
    {
        for ( j = 0 ; j < n ; j++ )
        {
            if ( (i&(1<<j)) != 0 )
            {
                for ( k = 0 ; k < graf[j].size() ; k++ )
                {
                    vecin = graf[j][k] ;
                    if ( (i&(1<<vecin)) == 0 )
                    {
                        dp[i|(1<<vecin)][vecin] = min(dp[i][j] + cost[j][vecin], dp[i|(1<<vecin)][vecin] ) ;
                    }
                }
            }
        }
    }
    int rez = 0x3f3f3f3f ;
    for ( i = 0 ; i < n ; i++ )
    {
        if ( cost[i][0] != 0x3f3f3f3f )
            rez = min(rez,dp[(1<<n)-1][i]+cost[i][0]) ;
    }
    fout << rez;
}

int main()
{
    citire() ;
    ciclu() ;
}