#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define sz(a) ((int)a.size())
#define pb push_back
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 3e3 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

vector<pii> G[maxn];
vector<int> pi[maxn];
int wage[maxn], pre[maxn], vis[maxn], n, m;

int fin(int x) {
    return x == pre[x] ? x : pre[x] = fin(pre[x]);
}
void merge(int s, int t) {
    if (sz(pi[s]) < sz(pi[t])) swap(s, t);
    for (auto &v : pi[t]) pi[s].pb(v);
    pre[t] = s;
}
int minCut(int &s, int &t, int cnt) {
    priority_queue<pii> q;
    for (int i = 1; i <= n; ++i) wage[i] = vis[i] = 0;
    t = 1;
    while (--cnt) {
        vis[s = t] = 1;
        for (auto &u : pi[s]) {
            for (auto &e : G[u]) {
                int v = fin(e.second), w = e.first;
                if (!vis[v]) q.push({ wage[v] += w, v });
            }
        }
        t = 0;
        while (!t) {
            if (q.empty()) return 0;
            auto e = q.top(); q.pop();
            if (wage[e.second] == e.first) t = e.second;
        }
    }
    return wage[t];
}
int SW() {
    for (int i = 1; i <= n; ++i) pre[i] = i, pi[i].clear(), pi[i].pb(i);
    int ret = inf;
    for (int i = n, s, t; i > 1; --i) {
        ret = min(ret, minCut(s, t, i));
        if (!ret) break;
        merge(s, t);
    }
    return ret;
}

int main(){

    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> n >> m){
        for(int i = 1; i <= n; ++i) G[i].clear();
        while(m--){
            int u, v, w; cin >> u >> v >> w;
            G[u].pb({w, v}), G[v].pb({w, u});
        }
        cout << SW() << "\n";
    }
    return 0;
}