K. Knight, Read The Problem Statement Carefully
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Are you familiar with Minimum Spanning Tree?

- No?

Ok. No problem. I'll teach you.

Minimum Spanning Tree(MST) is a subgraph in which each node is present and adds the original graph's minimum weight edge to form a tree.

More formally, you have to choose such a sub-graph that makes a tree and the sum of all edge weights is minimum.

Figure: Original Graph

We can generate a tree from the original graph like this :

Figure: A tree generated from the Original Graph

What is the sum of the edge weight in this tree?

5+4 = 9 . right?

Obviously yes is your answer. Can we generate another tree? Yes, we can. Here it is.

Figure: Another tree generated from the Original Graph
What is the sum of the edge weight in this tree?

Obviously 3+5 = 8.

But is that tree have the minimum sum of edge weight?

- No. So what is it? is it a minimum-spanning tree?

- No. These are spanning trees but not minimum spanning trees.

So what is the minimum spanning tree here? This is the minimum spanning tree given below:

Figure: Minimum Spanning Tree
The total edge weight of the tree is the minimum and it is 3+4 = 7.

Is it possible to create more than one minimum spanning tree?

Obviously possible. See this picture :

Let's dive into the original problem.

There is a given graph. Some nodes of the graph are black-colored, some nodes are red-colored and some nodes are white-colored.

Now you can do three operations exactly once:

  1. color the white color nodes to red,
  2. the red nodes to black, and
  3. the black nodes to white color.

Now you have to calculate how many edges there are in the graph if only red nodes are colored to the black and ignore the other two operations.

Input

The first line contains $$$n (3 \le n \le 2\cdot10^5)$$$ and $$$m$$$ $$${(n - 1 \le m \le min(2\cdot10^5, \frac{n(n-1)}{2}))}$$$ — the number of vertices in the graph and the number of edges of the graph.

Each of the next $$$m$$$ lines contains three integers $$$v$$$, $$$u$$$ and $$$w$$$ $$${( 1 \le u, v \le n, 1 \le w \le 10^9)}$$$ — the description of an edge and weight of the edge. You can assume that there will be no self-edge or multiple edges between the same nodes and the graph will be connected.

Output

Print the output in a single line.

Example
Input
3 3
1 2 1
2 3 2
3 1 3
Output
3
Note

If you don't understand the minimum spanning tree. See this example .

Read the statement Again and Again.