Connecting Cities: Minimum Roads Problem

You are given a kingdom consisting of n cities and a list of potential roads between some pairs of cities. In order to ensure that every pair of cities is connected directly or indirectly, a spanning tree must be built which has exactly n − 1 roads.

Even though some roads are already available with certain weights, the task is to determine the number of roads in a spanning tree that connects all the cities. Note that, by the very definition of a spanning tree in a connected graph, the answer is always n − 1.

Input Format: The first line will contain a single integer T denoting the number of test cases. For each test case, the first line contains two integers n and m representing the number of cities and the number of available roads respectively. The following m lines each contain three integers u, v, and w, which denote a road between cities u and v with weight w. The road details are provided for consistency although they do not affect the answer.

Output Format: For each test case, output a single integer on a new line indicating the number of roads in a spanning tree connecting all cities (which is always n − 1).

inputFormat

The input is read from standard input (stdin) and is in the following format:

• The first line contains an integer T, the number of test cases.
• For each test case:
  • The first line contains two integers n and m — the number of cities and the number of available roads.
  • The next m lines each contain three space-separated integers u, v, and w, describing a road between cities u and v with weight w.

Note: Even if road information is provided, the answer is always n − 1 for a connected spanning tree.

outputFormat

For each test case, output a single integer on a new line, which is the number of roads in a spanning tree connecting all the cities (i.e. n − 1).

The output should be written to standard output (stdout).

## sample

2
4 2
1 2 3
3 4 5
3 1
1 2 1

3
2

</p>