KOICOST - Cost

no tags 

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.

graph

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
anish1712: 2020-06-28 22:59:07

I removed SIGSEGV by adding
if(!m) return cout << 0, 0;

It passed too!

Last edit: 2020-06-28 22:59:42
luvkumbi: 2020-03-13 09:28:52

getting SIGSEGV ....any help?.....perfectly runs on my ide

nadstratosfer: 2020-03-01 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: 2020-02-26 13:54:37

undoubtedly the best mst problem on spoj
Some hints to those who are struggling to solve it :
1) Try to think it in reverse fashion like instead of deleting try to join nodes and create a maximum spanning tree.
2) Now to get to the answer think that what will be the contribution of a particular edge into the answer like how many times will this edge get into the answer. One crucial observation is that that a particular edge of wieght w will contribute to only those pairs (u,v) when w is the smallest edge in that path...

coolio_1: 2020-02-25 17:14:08

Take MOD 10^9 :)

himanshup: 2020-01-11 07:45:17

Why is the output of the sample test case is 256? I think it should be 246? Also, I am getting wrong answer for test case 20.:(

kesh4281: 2019-09-08 19:39:34

Even if ur output is wrong on TC1 then also spoj runs it till TC20 so don't assume that u got it wrong on last TC.

memito08: 2019-08-15 04:49:45

Is there anything that using modulo 10^9 obtained a correct answer in all tests?

abhinav_jain02: 2018-12-25 19:38:04

Interesting question with multiple concepts

Sigma Kappa: 2018-06-06 19:26:04

Shouldn't the answer to the sample test case be 246 rather than 256?


Added by:Lawl
Date:2011-06-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:2011 KOI Regional