/*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;
}
LyppbnB1dAo0IDMgCjEgMiAxMCAKMiAzIDIgCjMgNCA1IAoqLwojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGU8c3RkaW8uaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBwaWkgcGFpcjxsb25nIGxvbmcsbG9uZyBsb25nPgojZGVmaW5lIEYoaSxhLGIpIGZvcihsbCBpID0gKGxsKShhKTsgaSA8PSAobGwpKGIpOyBpKyspCiNkZWZpbmUgUkYoaSxhLGIpIGZvcihsbCBpID0gKGxsKShhKTsgaSA+PSAobGwpKGIpOyBpLS0pCiNkZWZpbmUgUEkgMy4xNDE1OTI2NQojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGZmIGZpcnN0CiNkZWZpbmUgc3Mgc2Vjb25kCiNkZWZpbmUgcGIoeCkgcHVzaF9iYWNrKHgpCiNkZWZpbmUgbXAoeCx5KSBtYWtlX3BhaXIoeCx5KQojZGVmaW5lIElORiAxMDAwMDAwMDA5CiNkZWZpbmUgbW9kIDEwMDAwMDAwMDAKbGwgaWRbMjAwMDA1XTsKbGwgc2l6ZVsyMDAwMDVdOwp2ZWN0b3IgPHBpaT4gZ1syMDAwMDVdOwp2b2lkIGluaXRpYWxpc2UoKQp7CglGKGksMSwyMDAwMDApCgl7CgkJaWRbaV09aTsKCQlzaXplW2ldID0gMTsKCX0KfQpsbCByb290KGxsIHgpCnsKCXdoaWxlKGlkW3hdIT14KQoJewoJCWlkW3hdID0gaWRbaWRbeF1dOwoJCXggPSBpZFt4XTsKCX0KCXJldHVybiB4Owp9CnZvaWQgVW5pb24obGwgYSxsbCBiKQp7CglsbCBwID0gcm9vdChhKTsKCWxsIHEgPSByb290KGIpOwoJaWYoc2l6ZVtwXTxzaXplW3FdKQoJewoJCWlkW3BdID0gaWRbcV07CgkJc2l6ZVtxXSArPSBzaXplW3BdOwoJfQoJZWxzZQoJewoJCWlkW3FdID0gaWRbcF07CgkJc2l6ZVtwXSArPSBzaXplW3FdOwoJfQp9CmludCBtYWluKCkgCnsKCXN0ZDo6aW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJaW5pdGlhbGlzZSgpOwoJbGwgbixtOwoJY2luPj5uPj5tOwoJbGwgbWF4dyA9IC0xOwoJRihpLDEsbSkKCXsKCQlsbCB1LHYsdzsKCQljaW4+PnU+PnY+Pnc7CgkJZ1t3XS5wYihtcCh1LHYpKTsKCQlnW3ddLnBiKG1wKHYsdSkpOwoJCW1heHcgPSBtYXgobWF4dyx3KTsKCX0KCWxsIHQgPSAwOwoJbGwgYW5zID0gMDsKCVJGKGksbWF4dywxKQoJewoJCWxsIHN6ID0gZ1tpXS5zaXplKCk7CgkJaWYoc3o+MCkKCQl7CgkJCWxsIHUgPSBnW2ldWzBdLmZmOwoJCQlsbCB2ID0gZ1tpXVswXS5zczsKCQkJLy9jb3V0PDx1PDwiICI8PHY8PCIgIjw8aTw8ZW5kbDsKCQkJbGwgcCxxOwoJCQlwID0gcm9vdCh1KTsKCQkJcSA9IHJvb3Qodik7CgkJCWlmKHAhPXEpCgkJCXsKCQkJCS8vY291dDw8c2l6ZVtwXTw8IiAiPDxzaXplW3FdPDwiICI8PHQ8PGVuZGw7CgkJCQlhbnMgPSAoYW5zJW1vZCArICgoKHNpemVbcF0pKihzaXplW3FdKSArIHQpKmkpJW1vZCklbW9kOwoJCQkJdCA9ICgoKHNpemVbcF0pKihzaXplW3FdKSklbW9kICsgdCVtb2QpJW1vZDsKCQkJCVVuaW9uKHUsdik7CgkJCX0KCQkJZWxzZQoJCQl7CgkJCQlhbnMgKz0gdCppOwoJCQkJYW5zJT1tb2Q7CgkJCX0KCQkJLypGKGksMSxuKQoJCQl7CgkJCQljb3V0PDxzaXplW2ldPDwiICI7CgkJCQkvL2NvdXQ8PGVuZGw7CgkJCX0qLwoJCQkvL2NvdXQ8PGVuZGw7CgkJfQoJfQoJY291dDw8YW5zPDxlbmRsOwoJcmV0dXJuIDA7Cn0=