Power Cables to Sewer Pipes

Several villages lie close together in one municipality. A windmill park supplies electricity to all of them, and a network of high-tension power cables connects every village to the park, either directly or indirectly through other villages. To guard against outages when a cable breaks, some redundant cables have been added between villages.

Meanwhile, all of the sewer pipes must be replaced, but there is a severe shortage of materials. The mayor therefore decides to strip out as much redundant cable as possible — accepting the loss of redundancy — and recycle it into sewer pipes, as long as every village stays connected. In other words, the cables left in place must still keep all villages connected to one another, and subject to that, the total length of removed cable is made as large as possible. The total length of redundant cable that can be removed never exceeds $400$ km.

At the metalworks, $1$ km of power cable yields $1$ m of sewer pipe, and the machines can only make pipes whose length is an integer number of meters. Let the total length of recycled cable be $S$ meters. The metalworks wants to know the number of ways to cut this $S$ meters into pipes of positive integer length, where the order of the pipes does not matter. For example, if $S = 3$, the ways are: one pipe of length $3$; one pipe of length $2$ and one of length $1$; and three pipes of length $1$ — three ways in total.

For each test case, determine this number of ways. If the power network has no redundancy at all, so that no cable can be removed, output $0$.

The first line contains the number of test cases $n$ ($0 < n \le 10000$).

Each test case is then given as follows:

• A line with one integer $m$ ($2 \le m \le 100$), the number of villages.
• A line with one integer $k$ ($1 \le k \le 1000$), the number of power cables.
• $k$ lines, each with three integers $f_i$, $t_i$, $l_i$ separated by spaces, indicating a power cable of length $l_i$ ($1 \le l_i \le 400$) km between village $f_i$ ($1 \le f_i \le m$) and village $t_i$ ($1 \le t_i \le m$).

For each test case, output on its own line the number of sewer-pipe combinations that can be made by recycling the maximum length of cable that can be removed without disconnecting any village from the power network. If the network is not redundant and no cable can be removed, output $0$.