#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>

#include <iomanip>

#define int long long

using namespace std;

string filename = "hamilton";

#ifdef LOCAL
    ifstream fin("input.in");
    ofstream fout("output.out");
#else
    ifstream fin(filename + ".in");
    ofstream fout(filename + ".out");
#endif

const int NMAX = 18;
const int INF= 1e9;

int dp[NMAX + 1][(1 << NMAX) + 1];

int cost[NMAX + 1][NMAX + 1];
vector <int> in[NMAX + 1];

signed main(){

    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        int a, b, c;
        fin >> a >> b >> c;
        cost[a][b] = c;
        in[b].push_back(a);
    }

    for(int i = 0; i < n; i++){
        for(int msk = 0; msk < (1 << n); msk++){
            dp[i][msk] = INF;
        }
    }
    dp[0][1] = 0;

    for(int msk = 1; msk < (1 << n); msk++){
        for(int i = 0; i < n; i++){
            if(msk & (1 << i)){
                for(int vec : in[i]){
                    if((1 << vec) & msk){
                        dp[i][msk] = min(dp[i][msk], dp[vec][msk ^ (1 << i)] + cost[vec][i]);
                    }
                }
            }
        }
    }

    int ans = INF;
    for(int vec : in[0]){
        ans = min(ans, dp[vec][(1 << n) - 1] + cost[vec][0]);
    }

    fout << ans << '\n';

    return 0;
}