#include<stdio.h>
#include<algorithm>
using namespace std;
const int MOD = 1e9;
typedef long long ll;
struct edge{
int st,en,len;
bool operator<(const edge &l)const{
return len<l.len;
}
}inp[100010];
int n, m;
ll ans;
ll now;
struct UnF{
int p[100010];
int w[100010];
void init(){for(int i=0;i<n;i++)p[i] = i, w[i] = 1;}
int Find(int x){
if(p[x] == x)return x;
return p[x] = Find(p[x]);
}
int Union(int x,int y){
x = Find(x), y = Find(y);
if(x==y)return (int)now;
now -= (ll)w[x] * (w[x] - 1) / 2 + (ll)w[y] * (w[y] - 1) / 2;
now += (ll)(w[x] + w[y]) * (w[x] + w[y] - 1) / 2;
now %= MOD;
if(w[x] > w[y])p[y] = x, w[x] += w[y];
else p[x] = y, w[y] += w[x];
return (int)now;
}
};
int main()
{
scanf("%d%d",&n,&m);
int i;
for(i=0;i<m;i++)scanf("%d%d%d",&inp[i].st,&inp[i].en,&inp[i].len);
sort(inp,inp+m);
UnF uf;
uf.init();
for(i=m-1;i>=0;i--)ans += (ll)inp[i].len * uf.Union(inp[i].st, inp[i].en), ans %= MOD;
printf("%lld",ans);
return 0;
}
