#include <stdio.h>
#include <algorithm>
using namespace std;
typedef pair <int,int> ppair;
pair <int,ppair> road[100001];
int n, m, anc[100001], cnt[100001], hab;
long long ans;
void input(void)
{
int i, x, y, w;
scanf("%d %d",&n,&m);
for(i=1 ; i<=m ; i++)
{
scanf("%d %d %d",&x,&y,&w);
hab+=w;
road[i]=make_pair(w,make_pair(x,y));
}
sort(road+1,road+m+1);
for(i=1 ; i<=n ; i++)
cnt[i]=1;
}
int find_anc(int x)
{
while(anc[x]>0)
{
x=anc[x];
}
return x;
}
void process(void)
{
int i, a1, a2;
for(i=m ; i>=1 ; i--)
{
a1=find_anc(road[i].second.first);
a2=find_anc(road[i].second.second);
if(a1!=a2)
{
ans+=(long long)cnt[a1]*cnt[a2]*hab;
ans%=1000000000;
if(a1<a2)
{
anc[a2]=a1;
cnt[a1]+=cnt[a2];
}
else
{
anc[a1]=a2;
cnt[a2]+=cnt[a1];
}
}
hab-=road[i].first;
}
}
void output(void)
{
printf("%lld",ans);
}
int main(void)
{
input();
process();
output();
return 0;
}
