/*
              `-/oo+/-   ``
            .oyhhhhhhyo.`od
           +hhhhyyoooos. h/
          +hhyso++oosy- /s
         .yoooossyyo:``-y`
          ..----.` ``.-/+:.`
                 `````..-::/.
                `..```.-::///`
               `-.....--::::/:
              `.......--::////:
             `...`....---:::://:
           `......``..--:::::///:`
          `---.......--:::::////+/`
          ----------::::::/::///++:
          ----:---:::::///////////:`
          .----::::::////////////:-`
          `----::::::::::/::::::::-
           `.-----:::::::::::::::-
             ...----:::::::::/:-`
               `.---::/+osss+:`
                 ``.:://///-.
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

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

const int INF = 1e9;

int hamiltonian(const vector <vector <pair <int, int>>> &g, int n) {
    vector <vector <int>> dp(n, vector <int>(1 << n, INF));
    dp[0][1] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        for (int node = 0; node < n; node++) {
            if (dp[node][mask] == INF || !(mask & (1 << node))) continue;

            for (auto it : g[node]) {
                if (!(mask & (1 << it.first)))
                    dp[it.first][mask | (1 << it.first)] = min(dp[it.first][mask | (1 << it.first)],
                                                                dp[node][mask] + it.second);
            }
        }
    }

    int ans = INF;
    for (int i = 1; i < n; i++) {
        for (auto it : g[i])
            if (it.first == 0)
                ans = min(ans, dp[i][(1 << n) - 1] + it.second);
    }

    return ans;
}

int main() {
    int n, m;
    in >> n >> m;
    vector <vector <pair <int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        in >> x >> y >> w;
        g[x].push_back(make_pair(y, w));
    }

    out << hamiltonian(g, n) << '\n';
    in.close();
    out.close();
    return 0;
}