#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
const int inf=1e9;
int n,m;
int id[100005],dg[100005],tot,pos[2050],d[4050],nxtw[2050],ct[100005];
vector<pii>road[100005];
vector<pii>Road[2005];
int dis[2005][2005];
ll Ans;
queue<int>q;
vector<int>vec[3050];
int tt,lf[3050],rg[3050];
void dfs(int u){
	pos[++tot]=u,dg[u]=-1;
	for(auto v:road[u])if(dg[v.fi]!=-1)dfs(v.fi);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int u,v;ll w;
		scanf("%d%d%d",&u,&v,&w);
		road[u].pb(mp(v,w)),road[v].pb(mp(u,w));
		++dg[u],++dg[v];
	}
	for(int i=1;i<=n;++i)ct[i]=1;
	for(int i=1;i<=n;++i)if(dg[i]==1)q.push(i);
	while(!q.empty()){
		int u=q.front();q.pop();dg[u]=-1;
		int v,w;for(auto v1:road[u])if(dg[v1.fi]>0)v=v1.fi,w=v1.se;
		--dg[v];Ans+=1ll*(n-ct[u])*ct[u]*w,ct[v]+=ct[u];
		if(!dg[v])cout<<Ans,exit(0);
		if(dg[v]==1)q.push(v);
	}
	for(int i=1;i<=n;++i)if(dg[i]>2)id[i]=++tot,pos[tot]=i;
	if(!tot){
		int Id=-1;
		for(int i=1;i<=n;++i)if(dg[i]>0)Id=i;
		dfs(Id);
		for(int i=1;i<=tot;++i){
			int Nxt=pos[i%tot+1];
			for(auto v:road[pos[i]])if(v.fi==Nxt)nxtw[i]=v.se;
		}
		for(int i=1;i<=tot+1;++i)d[i]=d[i-1]+nxtw[i-1];
		int cir=d[tot+1],x=cir/2;
		int sct=0,sct1=n;ll sum=0,sum1=0;int now=0;
		for(int i=1;i<=n;++i)sum1+=1ll*ct[pos[i]]*d[i];
		for(int i=1;i<=tot;++i){
			while(now<tot&&d[now+1]-d[i]<=x){++now,sct+=ct[pos[now]],sum+=1ll*ct[pos[now]]*d[now];}
			Ans+=1ll*ct[pos[i]]*sum-1ll*ct[pos[i]]*d[i]*sct;
			Ans+=-1ll*ct[pos[i]]*(sum1-sum)+1ll*ct[pos[i]]*(d[i]+cir)*(sct1-sct);
			sct-=ct[pos[i]],sct1-=ct[pos[i]];
			sum-=1ll*ct[pos[i]]*d[i],sum1-=1ll*ct[pos[i]]*d[i];
		} 
		cout<<Ans,exit(0);
	}
	
	cout<<Ans;
	return 0;
}