/*input
4 3 
1 2 10 
2 3 2 
3 4 5 
*/
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define pii pair<long long,long long>
#define F(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
#define RF(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); i--)
#define PI 3.14159265
#define ll long long
#define ff first
#define ss second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define INF 1000000009
#define mod 1000000000
ll id[200005];
ll size[200005];
vector <pii> g[200005];
void initialise()
{
	F(i,1,200000)
	{
		id[i]=i;
		size[i] = 1;
	}
}
ll root(ll x)
{
	while(id[x]!=x)
	{
		id[x] = id[id[x]];
		x = id[x];
	}
	return x;
}
void Union(ll a,ll b)
{
	ll p = root(a);
	ll q = root(b);
	if(size[p]<size[q])
	{
		id[p] = id[q];
		size[q] += size[p];
	}
	else
	{
		id[q] = id[p];
		size[p] += size[q];
	}
}
int main() 
{
	std::ios::sync_with_stdio(false);
	initialise();
	ll n,m;
	cin>>n>>m;
	ll maxw = -1;
	F(i,1,m)
	{
		ll u,v,w;
		cin>>u>>v>>w;
		g[w].pb(mp(u,v));
		g[w].pb(mp(v,u));
		maxw = max(maxw,w);
	}
	ll t = 0;
	ll ans = 0;
	RF(i,maxw,1)
	{
		ll sz = g[i].size();
		if(sz>0)
		{
			ll u = g[i][0].ff;
			ll v = g[i][0].ss;
			//cout<<u<<" "<<v<<" "<<i<<endl;
			ll p,q;
			p = root(u);
			q = root(v);
			if(p!=q)
			{
				//cout<<size[p]<<" "<<size[q]<<" "<<t<<endl;
				ans = (ans%mod + (((size[p])*(size[q]) + t)*i)%mod)%mod;
				t = (((size[p])*(size[q]))%mod + t%mod)%mod;
				Union(u,v);
			}
			else
			{
				ans += t*i;
				ans%=mod;
			}
			/*F(i,1,n)
			{
				cout<<size[i]<<" ";
				//cout<<endl;
			}*/
			//cout<<endl;
		}
	}
	cout<<ans<<endl;
	return 0;
}