Distinct Minimum Cut Values

In graph theory, the concept of a minimum cut is well known: for a given graph, any partition of its vertices into two non‐empty sets that separates two specific vertices s and t is called an s-t cut, and its capacity is defined as the sum of weights of edges crossing the partition. The s-t minimum cut is the cut with the smallest capacity among all s-t cuts.

In this problem, you are given an undirected connected weighted graph with N vertices and M edges. Consider the s-t minimum cut for every unordered pair of distinct vertices (there are N(N-1)/2 such pairs). Your task is to compute how many distinct minimum cut values exist among all these pairs.

Note: It is known that the Gomory–Hu tree of an undirected weighted graph can encode all minimum cut values between every pair of vertices. In fact, the minimum cut value between any two vertices is equal to the minimum weight edge on the unique path between them in the Gomory–Hu tree. Thus, the answer to the problem is the number of distinct weights among the N-1 edges of the Gomory–Hu tree.

inputFormat

The first line contains two integers, N and M, where N is the number of vertices and M is the number of edges.

Each of the following M lines contains three integers u, v, and w, indicating that there is an undirected edge between vertices u and v with weight w. The vertices are numbered from 1 to N, and the graph is guaranteed to be connected.

outputFormat

Output a single integer — the number of distinct minimum cut capacities among all pairs of vertices in the graph.

sample

4 3
1 2 3
2 3 5
3 4 3

2