## 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. 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 71 2 102 3 24 3 56 3 153 5 44 5 32 6 6

Output:
256
``` 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? Farhan: 2017-10-20 11:57:36 why the mod part is not mentioned in the question.. :/ take mod 1000000000 before printing the answer zurendra9: 2017-10-09 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 1. direct edge 2->6 2. 2->3->6 utkj97: 2017-06-20 11:02:44 Getting WA on case 20 even with modulo 10^9 :( free__bird: 2017-01-28 04:18:01 if getting wa on case 20 ,becauz mode = 1000000000 not 10e9+7 it's good question try to think reverse , instead of deleting ,join and instead of min. wt start from max wt :) Wumbolo: 2017-01-05 22:57:06 According to the Merriam-Webster dictionary entry for vertex, vertices and vertexes can be used as the plural of vertex, so verticies is *wrong*. zhzxcool: 2016-12-14 08:53:20 why i got wa on test20?sad :<