#include<bits/stdc++.h>
using namespace std;
inline int qread()
{
	int a=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){(a*=10)+=(ch^48);ch=getchar();}
	return a*f;
}
int n,m,cnt,tot,U[200010],V[200010],W[200010],deg[100010],siz[100010],del[100010],key[100010],id[100010];
int fr[3010],to[3010],C[3010],vis[100010],le[100010][2],dis[3010][3010];
long long ans,sum[100010][2],s[100010];
queue<int>que;
vector< pair<int,int> >e[100010],E[100010];
vector<int>S[3010];
inline int dfs(int rt,int ST,int da,int len)
{
	vis[rt]=1;
	if(da&&key[rt])
	{
		E[key[rt]].emplace_back(make_pair(key[ST],len));
		E[key[ST]].emplace_back(make_pair(key[rt],len));
		++tot;
		fr[tot]=rt;to[tot]=ST;C[tot]=len;
		return tot;
	}
	int p=0;
	for(pair<int,int>i:e[rt])
	{
		if(i.first==da)continue;
		if(!key[i.first]&&vis[i.first])continue;
		p=dfs(i.first,ST,rt,len+i.second);
		if(p&&rt^ST)
		{
			S[p].emplace_back(rt);
			le[rt][0]=len;
			le[rt][1]=C[p]-len;
		}
	}
	return p;
}
struct node
{
	int id,val;
}cx;
inline bool operator <(node x,node y){return x.val>y.val;}
priority_queue<node>qu;
inline void dij(int st,int *dis)
{
	memset(dis,63,(cnt+1)<<2);
	dis[st]=0;qu.push((node){st,0});
	while(!qu.empty())
	{
		cx=qu.top();qu.pop();
		if(cx.val^dis[cx.id])continue;
		for(pair<int,int>i:E[cx.id])if(dis[i.first]>cx.val+i.second)qu.push((node){i.first,dis[i.first]=cx.val+i.second});
	}
	return ;
}
int main()
{
	n=qread(),m=qread();
	for(int i=1,u,v,w;i<=m;++i)
	{
		++deg[U[i]=u=qread()],++deg[V[i]=v=qread()],W[i]=w=qread();
		e[u].emplace_back(make_pair(v,w));
		e[v].emplace_back(make_pair(u,w));
	}
	for(int i=1;i<=n;++i)
	{
		siz[i]=1;
		if(deg[i]<=1)que.push(i);
	}
	while(!que.empty())
	{
		++cnt;
		int p=que.front();que.pop();
		del[p]=1;
		for(pair<int,int>i:e[p])
		{
			if(--deg[i.first]==1)que.push(i.first);
			siz[i.first]+=siz[p];
			ans+=1ll*i.second*siz[p]*(n-siz[p]);
		}
	}
	if(cnt==n)
	{
		printf("%lld\n",ans);
		return 0;
	}
	for(int i=1;i<=n;++i)e[i].clear();
	for(int i=1;i<=m;++i)if(!del[U[i]]&&!del[V[i]])
	{
		e[U[i]].emplace_back(make_pair(V[i],W[i]));
		e[V[i]].emplace_back(make_pair(U[i],W[i]));
	}
	cnt=0;
	for(int i=1;i<=n;++i)if(deg[i]>=3)
	{
		key[i]=++cnt;
		id[cnt]=i;
	}
	if(!cnt)
	{
		for(int i=1;i<=n;++i)if(!del[i])
		{
			key[i]=++cnt;
			id[cnt]=i;
			break;
		}
	}
	for(int i=1;i<=cnt;++i)dfs(id[i],id[i],0,0);
	for(int i=1;i<=cnt;++i)dij(i,dis[i]);
	for(int i=1;i<=cnt;++i)for(int j=i+1;j<=cnt;++j)ans+=1ll*dis[i][j]*siz[id[i]]*siz[id[j]];
	for(int A=1,l,r,sz;A<=tot;++A)if(!S[A].empty())
	{
		l=fr[A],r=to[A];sz=S[A].size();
		for(int i=0;i<sz;++i)
		{
			sum[S[A][i]][0]=1ll*siz[S[A][i]]*le[S[A][i]][0];
			sum[S[A][i]][1]=1ll*siz[S[A][i]]*le[S[A][i]][1];
			s[S[A][i]]=siz[S[A][i]];
		}
		for(int i=1;i<sz;++i)
		{
			sum[S[A][i]][0]+=sum[S[A][i-1]][0];
			sum[S[A][i]][1]+=sum[S[A][i-1]][1];
			s[S[A][i]]+=s[S[A][i-1]];
		}
		for(int i=1,p=-1;i<sz;++i)
		{
			while(p+1<i&&le[S[A][i]][0]-le[S[A][p+1]][0]>=le[S[A][i]][1]+dis[key[l]][key[r]]+le[S[A][p+1]][0])++p;
			while(p>=0&&le[S[A][i]][0]-le[S[A][p]][0]<le[S[A][i]][1]+dis[key[l]][key[r]]+le[S[A][p]][0])--p;
			ans+=1ll*siz[S[A][i]]*(1ll*le[S[A][i]][0]*s[S[A][i-1]]-sum[S[A][i-1]][0]);
			if(p>=0)
			{
				ans+=1ll*siz[S[A][i]]*(1ll*(le[S[A][i]][1]+dis[key[l]][key[r]]-le[S[A][i]][0])*s[S[A][p]]);
				ans+=1ll*siz[S[A][i]]*(1ll*(sum[S[A][p]][0]+sum[S[A][p]][0]));
			}
		}
		for(int i=1;i<=cnt;++i)for(int j:S[A])ans+=1ll*siz[j]*siz[id[i]]*min(dis[i][key[l]]+le[j][0],dis[i][key[r]]+le[j][1]);
		for(int B=1,L,R,SZ,p,disL,disR;B<A;++B)if(!S[B].empty())
		{
			L=fr[B],R=to[B];
			SZ=S[B].size(),p=0;
			for(int i:S[A])
			{
				disL=min(dis[key[L]][key[l]]+le[i][0],dis[key[L]][key[r]]+le[i][1]);
				disR=min(dis[key[R]][key[l]]+le[i][0],dis[key[R]][key[r]]+le[i][1]);
				while(p>=1&&le[S[B][p-1]][0]+disL>=le[S[B][p-1]][1]+disR)--p;
				while(p+1<=SZ&&le[S[B][p]][0]+disL<le[S[B][p]][1]+disR)++p;
				ans+=1ll*siz[i]*(sum[S[B][SZ-1]][1]+disR*s[S[B][SZ-1]]);
				if(p)ans+=1ll*siz[i]*(sum[S[B][p-1]][0]-sum[S[B][p-1]][1]+(disL-disR)*s[S[B][p-1]]);
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}