#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],in[100005],dg[100005],tot,pos[100050],d[100050],nxtw[100050],ct[100005];
vector<pii>road[100005];
vector<pii>Road[10005];
int dis[4005][4005];
queue<int>q;
vector<int>vec[10050],Dis[10050];
int tt,lf[10050],rg[10050],sumw[10050];
void dfs(int u){
	pos[++tot]=u,dg[u]=-1;
	for(auto v:road[u])if(dg[v.fi]!=-1)dfs(v.fi);
}
struct Node{int u,_dis;};
bool operator<(Node a,Node b){return a._dis>b._dis;}
priority_queue<Node>pq;
void dj(int s){
	for(int i=1;i<=tot;++i)d[i]=inf;
	d[s]=0,pq.push(Node{s,0});
	while(!pq.empty()){
		Node now=pq.top();pq.pop();int u=now.u;if(d[u]<now._dis)continue;
		for(auto v:Road[u])if(d[v.fi]>d[u]+v.se)d[v.fi]=d[u]+v.se,pq.push(Node{v.fi,d[v.fi]});
	}
	for(int i=1;i<=tot;++i)dis[s][i]=d[i];
}
ll calc(){
	ll Ans=0;
	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=0;ll sum=0,sum1=0;int now=0;
	for(int i=1;i<=tot;++i)sum1+=1ll*ct[pos[i]]*d[i],sct1+=ct[pos[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];
	}
	return Ans;
}
int main(){
	ll Ans=0;
	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;
		}
		Ans+=calc();
		cout<<Ans,exit(0);
	}
	assert(tot<=3000); 
	for(int i=1;i<=tot;++i)
	    for(auto v:road[pos[i]]){
	    	if(id[v.fi])Road[i].pb(mp(id[v.fi],v.se));
			else if(!in[v.fi]&&dg[v.fi]>=0){
				++tt;int sw=v.se;
			    lf[tt]=i;int now=v.fi,lst=pos[i];
			    while(!id[now]){
			    	in[now]=1,vec[tt].pb(now),Dis[tt].pb(sw);int nxt;
			    	for(auto v:road[now])if(!in[v.fi]&&dg[v.fi]>=0&&v.fi!=lst){nxt=v.fi,sw+=v.se;break;}
			    	lst=now,now=nxt;
				}
				rg[tt]=id[now],sumw[tt]=sw;
				Road[i].pb(mp(id[now],sw));
				Road[id[now]].pb(mp(i,sw));
			}
		}
	for(int i=1;i<=n;++i)assert(in[i]||(dg[i]<0)||id[i]);
	assert(tt<=10000);
	for(int i=1;i<=tot;++i)dj(i);
	for(int i=1;i<=tot;++i)
	  for(int j=i+1;j<=tot;++j)Ans+=1ll*ct[pos[i]]*ct[pos[j]]*dis[i][j];
	for(int i=1;i<=tot;++i)
	  for(int j=1;j<=tt;++j)
	    for(int k=0;k<vec[j].size();++k)
	       Ans+=1ll*ct[pos[i]]*ct[vec[j][k]]*min(dis[i][lf[j]]+Dis[j][k],dis[i][rg[j]]+sumw[j]-Dis[j][k]);
	for(int i=1;i<=tt;++i)
	  for(int j=i+1;j<=tt;++j)
	    for(int k1=0;k1<vec[i].size();++k1)
	      for(int k2=0;k2<vec[j].size();++k2)
	        Ans+=1ll*ct[vec[i][k1]]*ct[vec[j][k2]]*min(min(dis[lf[i]][lf[j]]+Dis[i][k1]+Dis[j][k2],dis[lf[i]][rg[j]]+Dis[i][k1]+sumw[j]-Dis[j][k2]),min(dis[rg[i]][lf[j]]+sumw[i]-Dis[i][k1]+Dis[j][k2],dis[rg[i]][rg[j]]+sumw[i]-Dis[i][k1]+sumw[j]-Dis[j][k2]));
	for(int i=1;i<=tt;++i){
		int Now=dis[lf[i]][rg[i]]+Dis[i][0]+sumw[i]-Dis[i][(int)(Dis[i].size()-1)];
		tot=vec[i].size();
		for(int j=1;j<=tot;++j){
			pos[j]=vec[i][j-1];
			if(j<tot)nxtw[j]=Dis[i][j]-Dis[i][j-1];
			else nxtw[j]=Now;
		}
		Ans+=calc();
	}
	cout<<Ans;
	return 0;
}