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
Rajat De: 2015-02-24 11:30:54

You need to output the answer modulo 1000000000

Himanshu Dagar: 2015-01-25 14:14:55

I am unable to see the given picture :(
--Francky--> Visible again.

Last edit: 2015-01-25 15:01:18
suyog patil: 2013-02-20 06:01:06

standard problem!!!


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