/*
step1：在图G中找出任意 S-T最小割 cut-of-the-phase
step2：合并S、T，重复step1直至图G只剩下一个顶点
step3：过程中最小的cut-of-the-phase就是答案 
*/

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <numeric>
using namespace std;

typedef long long ll;

const int N = 3010;
const int M = 100010 << 1;
const int inf = 0x3f3f3f3f;

int head[N], val[N], idx;
int to[M], nex[M], weight[M];
bool vis[N];
int fa[N], link[N];
int n, m;

void init() {
    memset(head, -1, sizeof(head));
    memset(link, -1, sizeof(link));
    for(int i = 1; i <= n; ++i)
        fa[i] = i;
    idx = 0;
}

void add_edge(int u, int v, int w) {
    to[idx] = v; weight[idx] = w; nex[idx] = head[u]; head[u] = idx++;
}

int find(int u) { // 并查集
    return u == fa[u] ? u : fa[u] = find(fa[u]);
}

void merge(int u, int v) {
    int p = u;
    while (~link[p]) p = link[p];
    link[p] = v;
    fa[v] = u;
}

int MinimumCutPhase(int cnt, int &s, int &t) {
    memset(val, 0, sizeof(val));
    memset(vis, 0, sizeof(vis));
    priority_queue< pair<int, int> > q;
    t = 1;
    while (--cnt) {
        vis[s = t] = true;
        for (int u = s; ~u; u = link[u]) {
            for (int p = head[u]; ~p; p = nex[p]) {
                int v = find(to[p]);
                if (!vis[v])
                    q.push(make_pair(val[v] += weight[p], v));
            }
        }
        t = 0;
        while (!t) {
            if (q.empty()) return 0; // 图不连通
            auto pa = q.top(); q.pop();
            if (val[pa.second] == pa.first)
                t = pa.second;
        }
    }
    return val[t];
}

int StoerWagner() {
    int res = inf;
    for (int i = n, s, t; i > 1; --i) {
        res = min(res, MinimumCutPhase(i, s, t));
        if (res == 0)
            break;
        merge(s, t);
    }
    return res;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        init();
        for (int i = 0, u, v, w; i < m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            add_edge(u, v, w);
            add_edge(v, u, w);
        }
        printf("%d\n", StoerWagner());
    }
}