#include <fstream>
#include <vector>
#include <cstring>

#define INF 0x3f3f3f3f
using namespace std;

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

class Graph {
public:
    int node, cost;
};

vector <Graph> G[20];
int n, m, dp[20][(1 << 18) + 5], ret_road[20];

int main() {
    cin >> n >> m;
    memset(ret_road, INF, sizeof ret_road);

    for(int i = 1; i <= m; ++i) {
        int a, b, d;
        cin >> a >> b >> d;
        G[a].push_back({b, d});
        if(b == 0) {
            ret_road[a] = d;
        }
    }

    memset(dp, INF, sizeof dp);
    dp[0][1] = 0;

    for(int bitmask = 1; bitmask < (1 << n); bitmask += 2) {
        for(int frn = 0; frn < n; ++frn) {
            for(auto it: G[frn]) {
                int nxt_node = it.node;
                int nxt_cost = it.cost;

                if(!(bitmask & (1 << nxt_node))) {
                    dp[nxt_node][bitmask ^ (1 << nxt_node)] = min(dp[nxt_node][bitmask ^ (1 << nxt_node)], dp[frn][bitmask] + nxt_cost);
                }
            }
        }
    }

    int ans = INF;

    for(int i = 1; i < n; ++i) {
        ans = min(ans, dp[i][(1 << n) - 1] + ret_road[i]);
    }

    cout << ans << '\n';
    return 0;
}