#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 400010
int n, m, i, j, k, T;
int sze[N], f[N], u[N], v[N], w[N]; 
int lst, nw, vis[N], ans, x, y; 
set<pair<int, int> >G[N], conv; 
vector<pair<int, int> >E; 

int fa(int x) {
	if(f[x] == x) return x; 
	return f[x] = fa(f[x]); 
}

void del(int i) {
	conv.erase({w[i], i}); 
	G[u[i]].erase({v[i], i}); 
	G[v[i]].erase({u[i], i}); 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=m; ++i) {
		u[i]=read(); v[i]=read(); w[i]=read(); 
		if(u[i] > v[i]) swap(u[i], v[i]); 
		if(v[i]==u[i]+1 || (u[i]==1 && v[i]==n)) conv.insert({w[i], i}), debug("{%lld %lld}\n", w[i], i); 
		if(u[i]==1 && v[i]==n) swap(u[i], v[i]); 
		G[u[i]].insert({v[i], i}); 
		G[v[i]].insert({u[i], i}); 
	}
	while(!conv.empty()) {
		auto t = *conv.begin(); 
		vis[i=t.se]=1; del(i); 
		lst=v[i]; nw=u[i]; 
		debug(">> %lld | %lld %lld\n", i, u[i], v[i]); 
		while(nw!=v[i]) {
			debug("%lld %lld\n", lst, nw); 
			auto it = G[nw].upper_bound({lst, 1e9}); 
			if(it == G[nw].end()) it = G[nw].begin(); 
			j = it -> se; 
			if(conv.find({w[j], j})==conv.end()) {
				debug("============= {%lld %lld}\n", w[j], j); 
				w[j] += w[i];  
				conv.insert({w[j], j}); 
				if(u[j] != nw) swap(u[j], v[j]); 
			}
			else del(j), w[j]+=w[i]; 
			debug("find edge(%lld) : %lld -> %lld {%lld %lld}\n", j, v[j], u[j]); 
			lst = nw; nw = it->fi; 
		}
	}
	for(i=1; i<=n; ++i) f[i]=i, sze[i]=1; 
	for(i=1; i<=m; ++i) 
		if(!vis[i]) E.pb({w[i], i}), debug("Add %lld [%lld %lld]\n", w[i], u[i], v[i]);
	sort(E.begin(), E.end()); reverse(E.begin(), E.end()); 
	for(auto t : E) {
		i = t.se; 
		x = u[i]; y = v[i]; 
		ans += sze[fa(x)]*sze[fa(y)]*w[i]; 
		debug("%lld <-> %lld %lld %lld %lld[%lld %lld] \n", x, y, w[i], fa(x), fa(y), sze[fa(x)], sze[fa(y)]); 
		sze[fa(y)]+=sze[fa(x)]; f[fa(x)]=fa(y); 
	}
	printf("%lld", ans); 
	return 0;
}