#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
    long long w;
};

int N, M;
vector<Edge> edges;

map<pair<int, int>, long long> memo;

long long dfs(int used, int alice) {
    int turn = __builtin_popcount((unsigned)used);

    if (turn == N) {
        int bob = used ^ alice;

        long long score = 0;
        for (auto [u, v, w] : edges) {
            bool au = (alice >> u) & 1;
            bool av = (alice >> v) & 1;
            bool bu = (bob >> u) & 1;
            bool bv = (bob >> v) & 1;

            if (au && av) score += w;
            if (bu && bv) score -= w;
        }

        return score;
    }

    auto key = make_pair(used, alice);
    if (memo.count(key)) return memo[key];

    bool alice_turn = (turn % 2 == 0);

    long long res = alice_turn ? LLONG_MIN : LLONG_MAX;

    for (int v = 0; v < N; ++v) {
        if (used >> v & 1) continue;

        int nused = used | (1 << v);
        int nalice = alice;

        if (alice_turn) {
            nalice |= 1 << v;
        }

        long long val = dfs(nused, nalice);

        if (alice_turn) {
            res = max(res, val);
        } else {
            res = min(res, val);
        }
    }

    return memo[key] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    edges.resize(M);
    for (auto &[u, v, w] : edges) {
        cin >> u >> v >> w;
        --u;
        --v;
    }

    cout << dfs(0, 0) << '\n';
}