KOICOST  Cost
You are given an undirected graph with N verticies and M edges, where the weights are unique.
There is a function Cost(u, v), which is defined as follows:
While there is a path between vertex u and v, delete the edge with the smallest weight. Cost(u,v) is the sum of the weights of the edges that were deleted in this process.
For example, from the graph above (same as the sample input), Cost(2,6) is 2+3+4+5+6 = 20.
Given an undirected graph, your task is to calculate the sum of Cost(u,v) for all vertices u and v, where u < v. Since the answer can get large, output the answer modulo 10^9.
Input
The first line of the input consists of two integers, N and M. (1 <= N <= 100,000, 0 <= M <= 100,000)
The next M lines consists of three integers, u, v, and w. This means that there is an edge between vertex u and v with weight w. (1 <= u, v <= N, 1 <= w <= 100,000)
Output
Output the sum specified in the problem statement.
Example
Input: 6 7
1 2 10
2 3 2
4 3 5
6 3 15
3 5 4
4 5 3
2 6 6
Output: 256
hide comments
abhishekrahul:
20161208 17:04:07
best problem of dsu on spoj .............


cosmopoliton:
20160525 06:51:41
got a wa bcz of this incomplete input statement :(. 

Augusto:
20160321 23:55:11
Statement is incomplete :/ you need to print the answer modulo 10^9


bluefa:
20160318 23:56:46
don't use vector . it causes a segment fault 

Liquid_Science:
20160204 13:49:37
seems to get NZEC in java ,are the constraints correctly specified? 

fresh:
20150822 15:44:22
@chenzheng


chenzheng:
20150817 18:37:10
Who can tell me that when I input:


Uttam Kanodia:
20150601 19:22:58
Please update the problem for the Modulo and also the statement seems incomplete in the last line before the "Input" section. 

jkelava6:
20150224 19:58:26
Thanks! This modulo... 

Marin Kisic:
20150224 19:49:50
Thanks @Rajat De :) 
Added by:  Lawl 
Date:  20110601 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  2011 KOI Regional 