#include<bits/stdc++.h>
#define ll long long
#define pa pair<ll,int>
using namespace std;
const ll INF=1e18;
struct edge{
    int to,w;
};
int n,m;
vector<edge>G[3004];
int f[3004],lk[3004];
int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}
void Union(int x,int y){
    int p=x;
    while(lk[p])p=lk[p];
    lk[p]=y;
    f[y]=x;
}
ll val[3004];
bool vis[3004];
priority_queue<pa>q;
ll msp(int cnt,int &s,int &t){
    for(int i=1;i<=n;i++){
        vis[i]=0;
        val[i]=0;
    }
    while(!q.empty())q.pop();
    t=1;
    while(--cnt){
        vis[t]=1;
        s=t;
        for(int x=s;x;x=lk[x]){
            for(int i=0;i<G[x].size();i++){
                int to=Find(G[x][i].to),w=G[x][i].w;
                if(!vis[to]){
                    val[to]+=w;
                    q.push({val[to],to});
                }
            }
        }
        t=0;
        while(!t){
            if(q.empty())return 0;
            ll ft=q.top().first;
            int st=q.top().second;
            q.pop();
            if(val[st]==ft){
                t=st;
            }
        }
    }
    return val[t];
}
ll StoerWanger(){
    ll ans=INF;
    int s,t;
    for(int i=n;i>1;i--){
        ans=min(ans,msp(i,s,t));
        if(ans==0)break;
        Union(s,t);
    }
    return ans;
}
int w33ha(){
    for(int i=1;i<=n;i++){
        f[i]=i;
        lk[i]=0;
        G[i].clear();
    }
    for(int i=1;i<=m;i++){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        G[u].push_back((edge){v,w});
        G[v].push_back((edge){u,w});
    }
    printf("%lld\n",StoerWanger());
    return 0;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF)w33ha();
    return 0;
}