#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair <int,int> ppair;
queue <int> q;
pair <int,ppair> edge[100001];
vector <ppair> a[100001];
int n, m, check[100001], visit[100001];
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);
edge[i]=make_pair(w,make_pair(x,y));
}
sort(edge+1,edge+m+1);
for(i=1 ; i<=m ; i++)
{
a[edge[i].second.first].push_back(make_pair(edge[i].second.second,i));
a[edge[i].second.second].push_back(make_pair(edge[i].second.first,i));
}
}
int bfs(int start)
{
int i, j, now, cnt=0;
for(i=1 ; i<=n ; i++)
visit[i]=0;
q.push(start);
visit[start]=1;
cnt++;
while(!q.empty())
{
now=q.front();
q.pop();
j=a[now].size();
for(i=0 ; i<j ; i++)
if(visit[a[now][i].first]==0 && check[a[now][i].second]==0)
{
q.push(a[now][i].first);
visit[a[now][i].first]=1;
cnt++;
}
}
return cnt;
}
void process(void)
{
int i, x, y, hab=0;
for(i=1 ; i<=m ; i++)
{
hab+=edge[i].first;
check[i]=1;
x=bfs(edge[i].second.first);
if(visit[edge[i].second.second]==0)
{
y=bfs(edge[i].second.second);
ans+=(long long)x*y*hab;
ans%=1000000000;
}
}
}
void output(void)
{
printf("%lld",ans);
}
int main(void)
{
input();
process();
output();
return 0;
}
