#include <cstdio>
#include <algorithm>
struct data{
int x,y,w;
bool operator<(const data&r)const{
return w>r.w;
}
}path[100010];
int g[100010],cnt[100010],n;
long long int ans,w;
int seek(int nod){
if(g[nod]==nod)return nod;
return g[nod]=seek(g[nod]);
}
void merge(int a,int b){
a=seek(a);
b=seek(b);
if(a==b)
{
++n;
return;
}
ans+=w*cnt[a]*cnt[b];
g[b]=a;
cnt[a]+=cnt[b];
}
int main(){
int i,m,t;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i){
scanf("%d%d%d",&path[i].x,&path[i].y,&path[i].w);
w+=path[i].w;
}
std::sort(&path[1],&path[m+1]);
for(i=1;i<=n;++i)g[i]=i,cnt[i]=1;
for(i=1;i<n&&i<=m;++i){
merge(path[i].x,path[i].y);
w-=path[i].w;
ans%=1000000000;
}
printf("%d",ans);
return 0;
}
