#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;
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
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;
}