#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
const int M = 200005;
const int INF = 0x3f3f3f3f;
struct edge {
    int to, cost, next;
}g[M];
int cnt, head[N], link[N];
int par[N], dis[N];
bool vis[N];
void add_edge(int v, int u, int cost) {
    g[cnt].to = u, g[cnt].cost = cost, g[cnt].next = head[v], head[v] = cnt++;
}
int ser(int x) {
    int r = x, i = x, j;
    while(r != par[r]) r = par[r];
    while(par[i] != r) j = par[i], par[i] = r, i = j;
    return r;
}
void unite(int x, int y) {
    int p = x;
    while(~link[p]) p = link[p];
    link[p] = y;
    par[y] = x;
}
int min_cut_phase(int n, int &s, int &t) {
    memset(vis, false, sizeof vis);
    memset(dis, 0, sizeof dis);
    priority_queue<pair<int, int> > qu;
    t = 1;
    while(--n) {
        vis[s = t] = true;
        for(int i = s; ~i; i = link[i]) {
            for(int j = head[i]; ~j; j = g[j].next) {
                int v = ser(g[j].to);
                if(!vis[v]) qu.push(make_pair(dis[v] += g[j].cost, v));
            }
        }
        t = 0;
        while(!t) {
            if(qu.empty()) return 0;
            auto p = qu.top(); qu.pop();
            if(dis[p.second] == p.first) t = p.second;
        }
    }
    return dis[t];
}
int stoer_wagner(int n) {
    int ans = INF, s, t;
    for(int i = n; i > 1; i--) {
        ans = min(ans, min_cut_phase(i, s, t));
        if(ans == 0) break;
        unite(s, t);
    }
    return ans;
}
int main() {
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        for(int i = 1; i <= n; i++) par[i] = i;
        cnt = 0;
        memset(head, -1, sizeof head);
        memset(link, -1, sizeof link);
        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", stoer_wagner(n));
    }
    return 0;
}