#include <stdio.h>
#include <vector>
#include <algorithm>
#define MAX_V 100000
#define MAX_E 100000
class edge {
public:
edge(int from, int to, int weight)
{
_from = from;
_to = to;
_weight = weight;
}
int _from;
int _to;
int _weight;
};
bool operator<(const edge& x, const edge& y)
{
return x._weight > y._weight;
}
std::vector<edge> edges;
int uf[MAX_V + 1];
int rank[MAX_V + 1];
int adj[MAX_V + 1];
static int _find(int v1)
{
int tmp = v1;
while (v1 != uf[v1])
v1 = uf[v1];
uf[tmp] = v1;
return v1;
}
static unsigned int _union(int v1, int v2)
{
int ret = 0;
int pv1 = _find(v1);
int pv2 = _find(v2);
/* already connected */
if (pv1 == pv2) return ret;
ret = adj[pv1] * adj[pv2];
if (rank[pv1] > rank[pv2]) {
uf[pv2] = pv1;
adj[pv1] += adj[pv2];
}
else {
uf[pv1] = pv2;
adj[pv2] += adj[pv1];
if (rank[pv1] == rank[pv2])
rank[pv2]++;
}
return ret;
}
int main(void)
{
int nr_vertices, nr_edges;
unsigned long long sum = 0, total = 0;
scanf("%d %d", &nr_vertices, &nr_edges);
for (int i = 0; i < nr_edges; i++) {
int from, to, weight;
scanf("%d %d %d", &from, &to, &weight);
edges.push_back(edge(from, to, weight));
total += weight;
}
std::sort(edges.begin(), edges.end());
/* initialize uf */
for (int i = 1; i <= nr_vertices; i++) {
uf[i] = i;
adj[i] = rank[i] = 1;
}
for (std::vector<edge>::iterator iter = edges.begin(); iter != edges.end(); iter++) {
sum += _union(iter->_from, iter->_to) * total;
total -= iter->_weight;
}
printf("%llu\n", sum % 1000000000);
return 0;
}
