#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
int T;
void clear();
const int N=5010;
int n,m;
struct node
{
    int x,y,z;
}bs[N];
bool cmp(node a,node b){return a.z<b.z;}
int fa[N],sz[N];
bool mk[N];
int get(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=get(fa[x]);
}
bool merge(int x,int y)
{
    x=get(x);y=get(y);
    if(x==y) return 0;
    if(sz[x]>sz[y]) swap(x,y);
    fa[x]=y;sz[y]+=sz[x];
    return 1;
}
int solve(int cnt)
{
    int num=0;
    for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
    for(int i=1;i<=m;i++)
    {
        if(merge(bs[i].x,bs[i].y)==1)
        {
            num++;
            mk[i]=1;
        }
        else mk[i]=0;
    }
    for(int i=1;i<=m;i++) if(mk[i]==0&&num<cnt) num++,mk[i]=1;
    num=0;
    double res=0;
    for(int i=1;i<=m;i++) if(mk[i]) num++,res+=1.0*bs[i].z/num;
    return (int)(res+0.5);
}
void work()
{
    clear();
    n=re();m=re();
    for(int i=1;i<=m;i++) bs[i].x=re(),bs[i].y=re(),bs[i].z=re();
    sort(bs+1,bs+1+m,cmp);
    int ans=LONG_LONG_MAX;
    for(int cnt=n-1;cnt<=m;cnt++) ans=min(ans,solve(cnt));
    printf("%lld\n",ans);
    return;
}
signed main()
{
    freopen("tu.in","r",stdin);
    freopen("tu.out","w",stdout);
    T=1;
    while(T--) work();
    return 0;
}
void clear()
{
    return;
}