#include <stdio.h>
#include <algorithm>
struct edge{int x,y; long long c;} E[100010];
bool cmp(const edge& a, const edge& b){return a.c > b.c;}
const long long mod = 1000000000;
int N,M,P[100010]; long long C[100010],CON,ANS;
int find(int x){return P[x] = (x == P[x]) ? x : find(P[x]);}
int main()
{
int i,x,y;
scanf ("%d %d",&N,&M);
for (i=0;i<M;i++) scanf ("%d %d %lld",&E[i].x,&E[i].y,&E[i].c);
std::sort(E,E+M,cmp);
for (i=1;i<=N;i++){
P[i] = i;
C[i] = 1;
}
for (i=0;i<M;i++){
x = find(E[i].x);
y = find(E[i].y);
if (x != y){
P[y] = x;
CON = (CON + C[x] * C[y]) % mod;
C[x] += C[y];
}
ANS = (ANS + CON * E[i].c) % mod;
}
printf ("%lld",ANS);
return 0;
}
