Students who have studied graph theory are familiar with the concept of a minimum cut: for a given graph, a partition of the nodes into two sets is called an $s, t$-cut if nodes $s$ and $t$ are in different sets. For a weighted graph, the capacity of the cut is defined as the sum of the weights of the edges that have their endpoints in different sets. The minimum $s, t$-cut is the cut with the minimum capacity among all $s, t$-cuts.
For contestants preparing for the NOI, finding the minimum cut between two points in a weighted graph is no longer a difficult task. Let us broaden our perspective and consider the minimum cut capacities for all pairs of points in an undirected connected graph with $N$ nodes. There are a total of $\frac {N(N-1)} {2}$ such values. How many distinct values are there among them? This seems to be an interesting question.
Input
The first line of the input contains two integers $N$ and $M$, representing the number of nodes and the number of edges.
The next $M$ lines each contain three integers $u, v, w$, representing an edge between node $u$ and node $v$ (labeled starting from $1$) with weight $w$.
Output
The first line of the output contains an integer representing the number of distinct minimum cut capacities.
Subtasks
| Case # | $N$ | $M$ |
|---|---|---|
| 1 | $25$ | $150$ |
| 2 | $50$ | $500$ |
| 3 | $100$ | $1000$ |
| 4 | $150$ | $1500$ |
| 5 | $200$ | $2000$ |
| 6 | $300$ | $3000$ |
| 7 | $400$ | $4000$ |
| 8 | $500$ | $5000$ |
| 9 | $700$ | $7000$ |
| 10 | $850$ | $8500$ |
For all test cases, $w \leq 100000$.
Examples
Input 1
4 4 1 2 3 1 3 6 2 4 5 3 4 4
Output 1
3