#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#define N 100000
#define M 8000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data,snum;
};
struct node
{
	int x,y;
	bool operator < (const node &t)const
	{
		return x!=t.x?x<t.x:y<t.y;
	}
};
node st[N+1];
struct rds
{
	int num,data;
	bool operator < (const rds &t)const
	{
		return data>t.data;
	}
};
int n,m,lg[N+1],tfa[N+1],num[N+1],length,leng,tong[N+1],fa[N+1],nt[N+1],nt2[N+1],rst[N+1],sz[N+1],szt[N+1],dque[N+1],top;
long long depth[N+1],delta[N+1],delta2[N+1],ans,dis[M+1][M+1];
bool used[N+1],vis[N+1],vst[N+1],dst[N+1],vist[N+1];
vector<reads>E[N+1];
vector<reads>ES[N+1];
vector<int>v[N+1];
vector<int>cnt[N+1];
vector<int>cnt2[N+1];
map<node,int>p;
void add(int x,int y,int z,int w)
{
	E[x].push_back((reads){y,z,w}),E[y].push_back((reads){x,z,w});
	return;
}
void add2(int x,int y,int z)
{
	ES[x].push_back((reads){y,z}),ES[y].push_back((reads){x,z});
	return;
}
void dfs(int x)
{
	used[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i].num])
			depth[E[x][i].num]=depth[x]+E[x][i].data,fa[E[x][i].num]=x,vis[E[x][i].snum]=1,dfs(E[x][i].num);
	return;
}
void dfs2(int x)
{
	int cnt=0,y=0;
	dst[x]=vst[x];
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i].num]==x)
		{
			dfs2(E[x][i].num),dst[x]|=dst[E[x][i].num],cnt+=dst[E[x][i].num];
			if (dst[E[x][i].num]) y=E[x][i].num;
		}
	if (cnt>=2) vst[x]=1;
	else nt[x]=nt[y];
	if (vst[x]) nt[x]=nt2[x]=x;
	return;
}
void dfs3(int x)
{
	if (dst[x]) rst[x]=x;
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i].num]==x)
		{
			if (dst[E[x][i].num]) nt2[E[x][i].num]=nt2[x];
			rst[E[x][i].num]=rst[x],dfs3(E[x][i].num);
		}
	return;
}
void dijkstra(int x)
{
	int top;
	priority_queue<rds>q;
	for (int i=1;i<=length;++i) dis[x][i]=inf;
	q.push((rds){x,0}),dis[x][x]=0;
	while (!q.empty())
	{
		top=q.top().num,q.pop();
		if (used[top]) continue;
		used[top]=1;
		for (int i=0;i<E[top].size();++i)
			if (dis[x][E[top][i].num]>dis[x][top]+E[top][i].data)
				dis[x][E[top][i].num]=dis[x][top]+E[top][i].data,q.push((rds){E[top][i].num,dis[x][E[top][i].num]});
	}
	return;
}
bool cmp(int x,int y)
{
	return delta2[x]-delta[x]>delta2[y]-delta[y];
}
void dfs4(int x)
{
	dque[++top]=x,vist[x]=szt[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!vist[E[x][i].num]&&nt[x]==nt[E[x][i].num]&&nt2[x]==nt2[E[x][i].num])
			tfa[E[x][i].num]=E[x][i].data,dfs4(E[x][i].num),szt[x]+=szt[E[x][i].num];
	return;
}
int main()
{
	int x,y,z,ps;
	long long d1,d2,d3,d4,ds1,ds2;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	n=read(),m=read();
	for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),add(x,y,z,i);
	dfs(1);
	for (int i=1;i<=n;++i)
		for (int j=0;j<E[i].size();++j)
			if (!vis[E[i][j].snum])
				vst[i]=1;
	dfs2(1),dfs3(1);
	for (int i=1;i<=n;++i)
	{
		nt[i]=nt[rst[i]],nt2[i]=nt2[rst[i]];
		if (nt[i]) delta[i]=depth[i]-depth[nt[i]]+depth[i]-depth[rst[i]];
		if (nt2[i]) delta2[i]=depth[nt2[i]]-depth[i]+depth[i]-depth[rst[i]];
	}
	for (int i=1;i<=n;++i)
		if (vst[i])
			tong[++length]=i,num[i]=length;
	for (int i=1;i<=n;++i)
		for (int j=0;j<E[i].size();++j)
			if (!vis[E[i][j].snum])
				add2(num[i],num[E[i][j].num],E[i][j].data);
	for (int i=1;i<=length;++i)
		if (fa[tong[i]])
		    add2(i,num[rst[fa[tong[i]]]],depth[i]-depth[rst[fa[tong[i]]]]);
	for (int i=0;i<=length;++i) dis[0][i]=dis[i][0]=inf;
	for (int i=1;i<=length;++i) dijkstra(i);
	for (int i=1;i<=n;++i)
	{
	    if (p.find((node){nt[i],nt2[i]})==p.end()) st[++leng]=(node){nt[i],nt2[i]},p[(node){nt[i],nt2[i]}]=leng;
		v[p[(node){nt[i],nt2[i]}]].push_back(i);
	}
	for (int i=1;i<=length;++i)
	{
		sort(v[i].begin(),v[i].end(),cmp),cnt[i].resize(v[i].size()),cnt2[i].resize(v[i].size());
		for (int j=0;j<v[i].size();++j) cnt[i][j]=(j?cnt[i][j-1]:0)+delta[v[i][j]];
		for (int j=(int)(v[i].size())-1;j>=0;--j) cnt2[i][j]=(j+1!=v[i].size()?cnt2[i][j+1]:0)+delta2[v[i][j]];
	}
	for (int i=1;i<=leng;++i)
		for (int j=i+1;j<=leng;++j)
			if (!v[i].empty()&&!v[j].empty())
			{
				d1=dis[st[i].x][st[j].x],d2=dis[st[i].x][st[j].y],d3=dis[st[i].y][st[j].x],d4=dis[st[i].y][st[j].y];
				for (int k=0;k<v[i].size();++k)
				{
					ds1=min(delta[v[i][k]]+d1,delta2[v[i][k]]+d3),ds2=min(delta[v[i][k]]+d2,delta2[v[i][k]]+d4),ps=-1;
					for (int t=lg[v[j].size()];t>=0;--t)
						if (ps+(1<<t)<v[j].size()&&ds1+delta[v[j][ps+(1<<t)]]<ds2+delta2[v[j][ps+(1<<t)]])
							ps+=(1<<t);
					if (ps!=-1) ans+=1ll*ds1*(ps+1)+cnt[j][ps];
					if (ps!=v[j].size()) ans+=1ll*ds2*(v[j].size()-ps)+cnt2[j][ps+1];
				}
			}
	for (int i=1;i<=n;++i)
		if (!vis[i])
		{
			top=0,dfs4(i);
			for (int j=2;j<=top;++j) ans+=1ll*(szt[dque[1]]-szt[dque[j]])*szt[dque[j]]*tfa[dque[j]];
		}
	printf("%lld\n",ans);
	return 0;
}