#include <bits/stdc++.h>

using namespace std;

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

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

void citire()
{
    int i , x , y , c ;
    fin >> n >> m ;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> c ;
        graf[x].push_back(make_pair(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].first ;
                    if ( (i&(1<<vecin)) == 0 )
                    {
                        dp[i|(1<<vecin)][vecin] = min(dp[i][j] + graf[j][k].second , dp[i|(1<<vecin)][vecin] ) ;
                    }
                }
            }
        }
    }
    int rez = 0x3f3f3f3f ;
    for ( i = 0 ; i < n ; i++ )
        if ( graf[i][0].first == 0 )
            rez = min(rez,dp[(1<<n)-1][i]+graf[i][0].second) ;
    fout << rez;
}

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