#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long int LL;

const int maxn=,maxm=maxn*maxn/;

int w[maxn][maxn],dist[maxn],m,n,point[maxn];

bool intree[maxn];

int po(int x)

{

 if(x==point[x])return x;

     else return point[x]=po(point[x]);

}

void combine(int a,int b)

{

 a=po(a);b=po(b);

 bool counted[maxn];memset(counted,,sizeof(counted));

 for(int i=;i<n;i++)

     {

      int np=po(i);

      if((np==a)||(np==b)||(counted[np]))continue;

      counted[np]=true;

      w[np][a]+=w[np][b];w[a][np]+=w[b][np];

    }

 point[b]=a;

}

int main()

{

 ios::sync_with_stdio(false);

 while(scanf("%d%d",&n,&m)!=EOF)

     {

      memset(w,,sizeof(w));

      int a,b,c;

      for(int i=;i<m;i++)

          {

           scanf("%d%d%d",&a,&b,&c);

         w[a][b]+=c;w[b][a]+=c;

        }

     for(int i=;i<n;i++)

         point[i]=i;

     int ans=1e+;

     for(int ii=;ii<n;ii++)

         {

          if(ans==)break;

          memset(dist,,sizeof(dist));memset(intree,,sizeof(intree));

          int pre=po(),sum=;

          intree[pre]=true;

          while(sum<=(n-ii))

              {

               int maxk=-;

               bool counted[maxn];memset(counted,,sizeof(counted));

               for(int i=;i<n;i++)

                   {

                    int np=po(i);

                    if((intree[np])||(counted[np]))continue;

                    counted[np]=true;

                    dist[np]+=w[pre][np];

                    if((maxk==-)||(dist[np]>dist[maxk]))

                        {

                         maxk=np;

                    }

                }

             if(maxk==-){ans=;break;}

             intree[maxk]=true;

             if(sum==(n-ii))

                 {

                  combine(pre,maxk);

                  ans=min(ans,dist[maxk]);

                }

             pre=maxk;

             sum++;

            }

        }

     printf("%d\n",ans);

    }

 return ;

}