#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
#define MAX_N 20

int dp[1 << MAX_N][MAX_N];
int cost[MAX_N][MAX_N];
int N, M;

int main () {
    freopen ("hamilton.in", "r", stdin);
    freopen ("hamilton.out", "w", stdout);
    
    scanf ("%d %d", &N, &M);
    
    memset (cost, oo, sizeof (cost));
    FOR (i, 0, M) {
        int x, y, c;
        scanf ("%d %d %d", &x, &y, &c);
        
        cost[x][y] = c;
    }
    
    FOR (i, 0, (1 << N)) FOR (j, 0, N) dp[i][j] = oo;
    
    dp[1][0] = 0;
    FOR (i, 1, (1 << N)) FOR (j, 0, N) {
        if (dp[i][j] == oo) continue;
        FOR (k, 0, N) {
            if (((i >> k) & 1) || cost[j][k] == oo) continue;
            
            dp[i|(1 << k)][k] = min(dp[i|(1 << k)][k], dp[i][j] + cost[j][k]);
        }
    }
    int RESULT = dp[(1 << N) - 1][0];
    FOR (i, 1, N) RESULT = min (RESULT, dp[(1 << N) - 1][i] + cost[i][0]);
    
    printf ("%d\n", RESULT);
    
    return 0;
}