#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

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

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

int n, m, answer;
int g[NMAX][NMAX];
int dp[1 << NMAX][NMAX];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        g[a][b] = c;
    }

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

    dp[1][0] = 0;
    for(int mask = 1; mask < (1 << n); mask++) {
        if(__builtin_popcount(mask) == 1) {
            continue;
        }
        for(int i = 0; i < n; i++) {
            if(mask >> i & 1) {
                for(int j = 0; j < n; j++) {
                    if(i != j && g[j][i] && mask >> j & 1) {
                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + g[j][i]);
                    }
                }
            }
        }
    }

    answer = INF;
    for(int i = 1; i < n; i++) {
        if(g[i][0]) {
            answer = min(answer, dp[(1 << n) - 1][i] + g[i][0]);
        }
    }
    fout << answer << '\n';

    return 0;
}