#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 2000000
using namespace std;
namespace iobuff{
	const int LEN=1000000;
	char in[LEN+5], out[LEN+5];
	char *pin=in, *pout=out, *ed=in, *eout=out+LEN;
	inline char gc(void)
	{
		return pin==ed&&(ed=(pin=in)+fread(in, 1, LEN, stdin), ed==in)?EOF:*pin++;
	}
	inline void pc(char c)
	{
		pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out);
		(*pout++)=c;
	}
	inline void flush()
	{ fwrite(out, 1, pout-out, stdout), pout=out; }
	template<typename T> inline void scan(T &x)
	{
		static int f;
		static char c;
		c=gc(), f=1, x=0;
		while(c<'0'||c>'9') f=(c=='-'?-1:1), c=gc();
		while(c>='0'&&c<='9') x=10*x+c-'0', c=gc();
		x*=f;
	}
	template<typename T> inline void putint(T x, char div)
	{
		static char s[100];
		static int top;
		top=0;
		x<0?pc('-'), x=-x:0;
		while(x) s[top++]=x%10, x/=10;
		!top?pc('0'), 0:0;
		while(top--) pc(s[top]+'0');
		pc(div);
	}
}
using namespace iobuff;
struct reads
{
	int x,y;
	long long z;
	bool operator < (const reads &t)const
	{
		return x!=t.x?x>t.x:y<t.y;
	}
};
reads tong[N+1],dque[N+1];
struct node
{
	int num;
	long long data;
	bool operator < (const node &t)const
	{
		return data>t.data;	
	}
};
priority_queue<node>q;
int n,m,length,tops,deg[N+1],pv[N+1],pvt[N+1],rt[N+1],sz[N+1];
long long ans;
bool used[N+1];
vector<int>E[N+1];
bool cmp(reads a,reads b)
{
	return a.z>b.z;
}
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x),deg[x]++,deg[y]++;
	return;
}
int find(int x)
{
	if (rt[x]==x) return x;
	return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
	sz[y]+=sz[x],rt[x]=y;
	return;
}
int main()
{
	int top,x;
	scan(n),scan(m),length=m;
	for (int i=1;i<=m;++i)
	{
		scan(tong[i].x),scan(tong[i].y),scan(tong[i].z);
		if (tong[i].x>tong[i].y) swap(tong[i].x,tong[i].y);
	}
	sort(tong+1,tong+m+1);
	for (int i=1;i<=m;++i)
	{
		if (tong[i].x+1!=tong[i].y)
		{
			++length,add(i,length),x=tong[i].y;
			while (x!=tong[i].x) add(pvt[x],length),x=pv[x];
		}
		pv[tong[i].y]=tong[i].x,pvt[tong[i].y]=i;
	}
	for (int i=1;i<=m;++i)
		if (deg[i]==1)
			q.push((node){i,tong[i].z});
	while (!q.empty())
	{
		top=q.top().num,q.pop();
		if (!deg[top]) continue;
		used[top]=1,deg[top]=0;
		for (int i=0;i<E[top].size();++i)
			if (deg[E[top][i]])
			{
				deg[E[top][i]]=0;
				for (int j=0;j<E[E[top][i]].size();++j)
					if (E[E[top][i]][j]!=top)
					{
						deg[E[E[top][i]][j]]--,tong[E[E[top][i]][j]].z+=tong[top].z;
						if (deg[E[E[top][i]][j]]==1) q.push((node){E[E[top][i]][j],tong[E[E[top][i]][j]].z});
					}
			}
	}
	for (int i=1;i<=m;++i)
		if (!used[i])
			dque[++tops]=tong[i];
	for (int i=1;i<=n;++i) rt[i]=i,sz[i]=1;
	sort(dque+1,dque+tops+1,cmp);
	for (int i=1;i<=tops;++i) ans+=1ll*sz[find(dque[i].x)]*sz[find(dque[i].y)]*dque[i].z,unionn(find(dque[i].x),find(dque[i].y));
	printf("%lld\n",ans);
	return 0;
}