#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <cmath>

#define MOD 666013
#define INT_MAX 1000000000

using namespace std ;

ifstream cin ("hamilton.in") ;
ofstream cout ("hamilton.out") ;

int n, cost[19][19] ;

vector<pair<int, int> > m[19] ;

int dp[1 << 18][19] ;

int main()
{
    int q ;

    cin >> n >> q ;

    for(int f = 0 ; f < n ; f ++)
        for(int e = 0 ; e < n ; e ++)
            cost[f][e] = INT_MAX / 3 ;

    while(q --)
    {
        int a, b, c ;

        cin >> a >> b >> c ;

        m[b].push_back({a, c}) ; /// putem ajunge in b din nodurile m[b]

        cost[a][b] = c ;
    }

    for(int f = 0 ; f < 1 << n ; f ++)
        for(int e = 0 ; e < n ; e ++)
            dp[f][e] = INT_MAX / 3 ;

    dp[1][0] = 0 ;

    for(int f = 0 ; f < (1 << n) ; f ++)
        for(int k = 0 ; k < n ; k ++)
            if(f & (1 << k)) /// nodul k se gaseste in bitmask
                for(int i = 0 ; i < m[k].size() ; i ++)
                {
                    int v = m[k][i].first ;

                    if(f & (1 << v)) /// trebe sa fie si v in f
                        dp[f][k] = min(dp[f][k], dp[f ^ (1 << k)][v] + m[k][i].second) ;
                }
/*
    for(int f = 0 ; f < 1 << n ; f ++)
    {
        cout << f << "       " ;
        for(int e = 0 ; e < n ; e ++)
            cout << dp[f][e] << " " ;

        cout << endl ;
    }

    return 0 ;
*/
    int mn = INT_MAX ;

    for(int f = 0 ; f < n ; f ++)
        mn = min(mn, dp[(1 << n) - 1][f] + cost[f][0]) ;

    cout << mn ;

    return 0 ;
}
/// 1990