#include <cstdio>
#include <algorithm>
using namespace std;
struct edge{int s,e,x;}a[100005];
int cmp(edge a, edge b){return a.x > b.x;}
int p[100005],r[100005],sz[100005],n,m;
long long sum[100005];
void init(){
for (int i=1; i<=n; i++) p[i] = i, sz[i] = 1;
}
int fnd(int x){
if(p[x] == x) return x;
else return p[x] = fnd(p[x]);
}
void uni(int x, int y){
x = fnd(x);
y = fnd(y);
if(r[x] > r[y]) p[x] = y, sz[y] += sz[x];
else p[y] = x, sz[x] += sz[y];
if(r[x] == r[y]) r[y]++;
}
int main(){
scanf("%d %d",&n,&m);
for (int i=0; i<m; i++) {
scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].x);
}
sort(a,a+m,cmp);
init();
sum[0] = a[0].x;
for (int i=1; i<=m; i++) {
sum[i] = sum[i-1] + a[i].x;
}
long long res = 0;
for (int i=0; i<m; i++) {
if(fnd(a[i].s) == fnd(a[i].e)) continue;
else{
res += (sum[m] - (i?sum[i-1]:0))*sz[fnd(a[i].s)] * sz[fnd(a[i].e)];
uni(a[i].s,a[i].e);
}
res %= 1000000000;
}
printf("%lld",res);
}
