// 那就是希望。
// 即便需要取模，也是光明。

#include <algorithm>
#include <queue>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
// Your shadow Gets in the way of my light
std::vector<std::pair<uint,uint> >Way[100005];
std::vector<uint>As[5005],Ds[5005];
uint U[5005],V[5005],W[5005],cnt;
uint Deg[100005],A[100005],Id[100005],Dist[2005][2005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    uint n,m;ullt ans=0;scanf("%u%u",&n,&m);
    while(m--){uint u,v,w;scanf("%u%u%u",&u,&v,&w),Way[--u].push_back({--v,w}),Way[v].push_back({u,w});}
    std::vector<uint>Q;
    for(uint i=0;i<n;A[i++]=1)if((Deg[i]=Way[i].size())==1)Q.push_back(i);
    while(Q.size())
    {
        uint p=Q.back();Deg[p]=0,Q.pop_back();
        for(auto s:Way[p])if(Deg[s.first])
        {
            ans+=(ullt)s.second*A[p]*(n-A[p]),A[s.first]+=A[p],A[p]=0;if(--Deg[s.first]==1)Q.push_back(s.first);
        }
    }
    for(uint i=0;i<n;i++)if(Deg[i])
    {
        std::vector<std::pair<uint,uint> >Now;
        for(auto s:Way[i])if(Deg[s.first])Now.push_back(s);
        Way[i]=Now,Id[i]=-1;
        if(Q.empty()||Deg[i]>2)Deg[i]=-1,Id[i]=Q.size(),Q.push_back(i);
    }
    for(uint i=0;i<n;i++)if(!~Deg[i])
        for(auto s:Way[i])if(!~Deg[s.first]&&i<s.first)
            U[cnt]=Id[i],V[cnt]=Id[s.first],W[cnt++]=s.second;
    if(Q.empty())return printf("%llu\n",ans),0;
    for(uint i=0;i<n;i++)if(Deg[i]&&~Deg[i])
    {
        uint u=i,lst=Way[i][0].first;
        while(~Deg[u])
            Deg[u]=0,As[cnt].push_back(A[u]),
            Ds[cnt].push_back(Way[u][Way[u][0].first==lst].second),
            std::swap(u,lst=Way[u][Way[u][0].first==lst].first);
        U[cnt]=Id[u];
        std::reverse(As[cnt].begin(),As[cnt].end()),std::reverse(Ds[cnt].begin(),Ds[cnt].end());
        u=i,lst=Way[i][1].first,As[cnt].pop_back();
        while(~Deg[u])
            Deg[u]=0,As[cnt].push_back(A[u]),
            Ds[cnt].push_back(Way[u][Way[u][0].first==lst].second),
            std::swap(u,lst=Way[u][Way[u][0].first==lst].first);
        V[cnt]=Id[u];
        for(auto&s:Ds[cnt])s=W[cnt]+=s;
        cnt++;
    }
    // for(uint i=0;i<cnt;i++)
    //     printf("%u %u %u\n",U[i]+1,V[i]+1,W[i]);
    n=Q.size();
    for(uint i=0;i<n;i++)Way[i].clear(),A[i]=A[Q[i]];
    for(uint i=0;i<cnt;i++)Way[U[i]].push_back({V[i],W[i]}),Way[V[i]].push_back({U[i],W[i]});
    for(uint i=0;i<n;i++)
    {
        static bol G[2005];
        for(uint j=0;j<n;j++)Dist[i][j]=i==j?0:2e9,G[j]=false;
        std::priority_queue<std::pair<uint,uint>,
                std::vector<std::pair<uint,uint> >,std::greater<std::pair<uint,uint> > >Q;
        Q.push({0,i});
        while(Q.size())
        {
            uint p=Q.top().second;Q.pop();if(G[p])continue;
            G[p]=true;
            for(auto s:Way[p])if(_min(Dist[i][s.first],Dist[i][p]+s.second))Q.push({Dist[i][s.first],s.first});
        }
        for(uint j=i+1;j<n;j++)ans+=(ullt)Dist[i][j]*A[i]*A[j];
    }
    for(uint i=0;i<n;i++)for(uint j=0;j<cnt;j++)for(uint k=0;k<As[j].size();k++)
        ans+=(ullt)std::min(Ds[j][k]+Dist[i][U[j]],W[j]-Ds[j][k]+Dist[i][V[j]])*A[i]*As[j][k];
    for(uint i=0;i<cnt;i++)
    {
        uint c=0,c_all=0;ullt s=0,s_all=0;uint len=Dist[U[i]][V[i]]+W[i];
        for(uint j=0;j<As[i].size();j++)c_all+=As[i][j],s_all+=(ullt)Ds[i][j]*As[i][j];
        for(uint j=0,k=0;j<As[i].size();j++)
        {
            c-=As[i][j],s-=(ullt)Ds[i][j]*As[i][j],c_all-=As[i][j],s_all-=(ullt)Ds[i][j]*As[i][j];
            while(k<As[i].size()&&(Ds[i][k]-Ds[i][j])*2<=len)c+=As[i][k],s+=(ullt)Ds[i][k]*As[i][k],k++;
            ans+=As[i][j]*(s-(ullt)c*Ds[i][j]+(ullt)(c_all-c)*(len+Ds[i][j])-(s_all-s));
        }
    }
    // for(uint i=0;i<cnt;i++)for(uint j=i+1;j<cnt;j++)
    //     for(uint p=0;p<As[i].size();p++)for(uint q=0;q<As[j].size();q++)
    //         ans+=(ullt)As[i][p]*As[j][q]*
    //                 std::min({Dist[U[i]][U[j]]+Ds[i][p]+Ds[j][q],Dist[U[i]][V[j]]+Ds[i][p]+W[j]-Ds[j][q],
    //                     Dist[V[i]][U[j]]+W[i]-Ds[i][p]+Ds[j][q],Dist[V[i]][V[j]]+W[i]-Ds[i][p]+W[j]-Ds[j][q]});
    for(uint i=0;i<cnt;i++)for(uint j=i+1;j<cnt;j++)
    {
        ullt w,w2;uint c=0,c_all=0;for(auto s:As[j])c+=s,c_all+=s;
        for(uint q=w=0;q<As[j].size();q++)
            w+=(ullt)std::min(Ds[j][q]+Dist[U[i]][U[j]],(W[j]-Ds[j][q])+Dist[U[i]][V[j]])*As[j][q];
        for(uint p=0;p<As[i].size();p++)
            if(Dist[U[i]][U[j]]+Ds[i][p]<=Dist[V[i]][U[j]]+W[i]-Ds[i][p]
                        &&Dist[U[i]][V[j]]+Ds[i][p]<=Dist[V[i]][V[j]]+W[i]-Ds[i][p])
                ans+=As[i][p]*((ullt)Ds[i][p]*c+w);
        for(uint q=w=0;q<As[j].size();q++)
            w+=(ullt)std::min(Ds[j][q]+Dist[V[i]][U[j]],(W[j]-Ds[j][q])+Dist[V[i]][V[j]])*As[j][q];
        for(uint p=0;p<As[i].size();p++)
            if(Dist[U[i]][U[j]]+Ds[i][p]>Dist[V[i]][U[j]]+W[i]-Ds[i][p]
                        &&Dist[U[i]][V[j]]+Ds[i][p]>Dist[V[i]][V[j]]+W[i]-Ds[i][p])
                ans+=As[i][p]*((ullt)(W[i]-Ds[i][p])*c+w);
        for(uint q=w=w2=0;q<As[j].size();q++)w+=(ullt)Ds[j][q]*As[j][q];
        for(uint p=0,q=As[i].size()-1;p<As[i].size();p++)
            if(Dist[U[i]][U[j]]+Ds[i][p]<=Dist[V[i]][U[j]]+W[i]-Ds[i][p]
                        &&Dist[U[i]][V[j]]+Ds[i][p]>Dist[V[i]][V[j]]+W[i]-Ds[i][p])
            {
                while(~q&&Dist[U[i]][U[j]]+Ds[i][p]+Ds[j][q]>=Dist[V[i]][V[j]]+W[i]-Ds[i][p]+W[j]-Ds[j][q])
                    w-=(ullt)Ds[j][q]*As[j][q],c-=As[j][q],w2+=(ullt)(W[j]-Ds[j][q])*As[j][q],q--;
                ans+=As[i][p]*(w+w2+(ullt)c*(Dist[U[i]][U[j]]+Ds[i][p])
                                    +(ullt)(c_all-c)*(Dist[V[i]][V[j]]+W[i]-Ds[i][p]));
            }
        c=c_all;
        for(uint q=w=w2=0;q<As[j].size();q++)w+=(ullt)(W[j]-Ds[j][q])*As[j][q];
        for(uint p=0,q=0;p<As[i].size();p++)
            if(Dist[U[i]][U[j]]+Ds[i][p]>Dist[V[i]][U[j]]+W[i]-Ds[i][p]
                        &&Dist[U[i]][V[j]]+Ds[i][p]<=Dist[V[i]][V[j]]+W[i]-Ds[i][p])
            {
                for(uint q=0;q<As[j].size();q++)ans+=(ullt)As[i][p]*As[j][q]*
                    std::min({Dist[U[i]][U[j]]+Ds[i][p]+Ds[j][q],Dist[U[i]][V[j]]+Ds[i][p]+W[j]-Ds[j][q],
                        Dist[V[i]][U[j]]+W[i]-Ds[i][p]+Ds[j][q],Dist[V[i]][V[j]]+W[i]-Ds[i][p]+W[j]-Ds[j][q]});
                // while(q<As[i].size()&&Dist[V[i]][U[j]]+W[i]-Ds[i][p]+Ds[j][q]<=
                //                     Dist[U[i]][V[j]]+Ds[i][p]+W[j]-Ds[j][q])
                //     w-=(ullt)(W[j]-Ds[j][q])*As[j][q],c-=As[j][q],w2+=(ullt)Ds[j][q]*As[j][q],q++;
                // ans+=As[i][p]*(w+w2+(ullt)c*(Dist[U[i]][V[j]]+Ds[i][p])
                //                     +(ullt)(c_all-c)*(Dist[V[i]][U[j]]+W[i]-Ds[i][p]));
            }
    }
    printf("%llu\n",ans);
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。