#include <iostream>
#include <vector>
#include <fstream>
#define MAXMASK 300000
#define MAXN    20
#define INF     1640000000
using namespace std;
int n,m,x,y,cost;
long long dp[MAXMASK][MAXN],f[MAXN];
vector<pair<int, int>> L[MAXN];

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

int main()
{
    fin >> n >> m;
    /// intializam toate valorile dp cu INF
    for(int codStare = 1; codStare < (1<<n); codStare += 2){
        for(int last = 0; last < n; last++){
            dp[codStare][last] = INF;
        }
    }
    /// citim, realizam lista de vecini
    for(int i = 1; i <= m; i++){
        fin >> x >> y >> cost;
        L[x].push_back({y, cost});
        if(y == 0){
            f[x] = cost;
        }
    }
    dp[1][0] = 0;
    for(int codStare = 1; codStare < (1<<n); codStare += 2){
        for(int last = 0; last < n; last++){
            if(dp[codStare][last] != INF){
                for(int i = 0; i < L[last].size(); i++){
                    int x = L[last][i].first;
                    int cost = L[last][i].second;
                    if( ( (codStare >> last) & 1 ) == 1 ){
                        dp[codStare+(1<<x)][x] = min(dp[codStare+(1<<x)][x], dp[codStare][last]+cost);
                    }
                }
            }
        }
    }
    long long sol = INF;
    for(int last = 1; last < n; last++){
        if(f[last] != 0 && dp[(1<<n)-1][last] != INF){
            sol = min(sol, dp[(1<<n)-1][last]+f[last]);
        }
    }
    fout << sol << "\n";
    return 0;
}