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
abhinav_jain02:
20181225 19:38:04
Interesting question with multiple concepts


Sigma Kappa:
20180606 19:26:04
Shouldn't the answer to the sample test case be 246 rather than 256? 

Farhan:
20171020 11:57:36
why the mod part is not mentioned in the question.. :/ take mod 1000000000 before printing the answer 

zurendra9:
20171009 07:39:19
Can someone explain me the sample test case? I can only see 2 path to 2>6 in the sample input . that are


utkj97:
20170620 11:02:44
Getting WA on case 20 even with modulo 10^9 :(


free__bird:
20170128 04:18:01
if getting wa on case 20 ,becauz mode = 1000000000 not 10e9+7


Wumbolo:
20170105 22:57:06
According to the MerriamWebster dictionary entry for vertex, vertices and vertexes can be used as the plural of vertex, so verticies is *wrong*. 

zhzxcool:
20161214 08:53:20
why i got wa on test20?sad :< 

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 :(. 
Added by:  Lawl 
Date:  20110601 
Time limit:  0.175s0.876s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  2011 KOI Regional 