#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
#define MOD 1000000000
#define ll long long
int N, M, p[100005], s[100005];
pair<int,pair<int,int> > g[100005];
ll res = 0, curr = 0;
ll C(int n) {return ((ll)n)*(n-1)/2;}
int find(int n) {
if(p[n] == 0) return n;
return p[n] = find(p[n]);
}
void make_union(int n1, int n2, int w) {
int p1 = find(n1), p2 = find(n2);
if(p1 == p2) {
res += w*curr;
res %= MOD;
return;
}
curr -= C(s[p1])+C(s[p2]);
curr += C(s[p1]+s[p2]);
if(p1<p2) {
p[p2] = p1;
s[p1] += s[p2];
}
else {
p[p1] = p2;
s[p2] += s[p1];
}
res += w*curr;
res %= MOD;
}
int main() {
scanf("%d %d",&N,&M);
fill(s,s+1+N,1);
for(int i = 1;i<=M;++i) {
int n1, n2, w;
scanf("%d %d %d",&n1,&n2,&w);
g[i] = make_pair(w,make_pair(n1,n2));
}
sort(g+1,g+1+M);
for(int i = M;i>=1;--i) {
make_union(g[i].second.first,g[i].second.second,g[i].first);
}
printf("%lld\n",res);
return 0;
}
