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
jeaf_dean:
20210605 15:57:30
"While there is a path between vertex u and v, delete the edge with the smallest weight" doesn't imply weight in a given path.


greenindia:
20210306 18:19:25
i think its the best question on dsu 

lamda_cdm_10:
20210226 17:07:10
Beautiful problem on DSU . Enjoy solving it !!


iamfarraz:
20201102 22:18:06
why sigabrt : ((( 

worrywart_ind:
20201013 17:51:10
https://www.youtube.com/watch?v=XaVUt9pC3t0 

anish1712:
20200628 22:59:07
I removed SIGSEGV by adding


luvkumbi:
20200313 09:28:52
getting SIGSEGV ....any help?.....perfectly runs on my ide 

nadstratosfer:
20200301 22:12:29
From TLE in C to AC in pure Python =) Great problem, came upon more ideas just improving my code here than I usually get solving several tasks. 

kushagra_2:
20200226 13:54:37
undoubtedly the best mst problem on spoj


coolio_1:
20200225 17:14:08
Take MOD 10^9 :) 
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 