#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <numeric>
#define LL long long
#define PII pair<int,int>
using namespace std;

const int MAXV=3010;
const int MAXE=200010*2;
const int INF=0x3f3f3f3f;

int head[MAXV], val[MAXV], ecnt;
int to[MAXE], nxt[MAXE], weight[MAXE];
bool vis[MAXV];
int fa[MAXV], link[MAXV];
int n,m;

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

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

int findset(int u) {
    return u == fa[u] ? u : fa[u] = findset(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 + 1, 0, sizeof(int) * n);
    memset(vis + 1, 0, sizeof(bool) * n);
    priority_queue<PII> que;
    t = 1;
    while (--cnt) {
        s=t;
        vis[s]=true;
        for (int u = s; ~u; u = link[u]) {
            for (int p = head[u]; ~p; p = nxt[p]) {
                int v = findset(to[p]);
                if (!vis[v]){
                    val[v] += weight[p];
                    que.push(make_pair(val[v], v));
                }
            }
        }
        t = 0;
        while (!t) {
            if (que.empty()) return 0;
            PII pa = que.top(); que.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) != EOF) {
        init();
        int u,v,w;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            add_edge(u, v, w);
        }
        printf("%d\n", StoerWagner());
    }
}