P2143 [JSOI2010] Massive Bonus

The rapid development of NJ City benefits from its convenient transportation. However, as the economy grows, many people move into NJ City, and its transportation comes under heavy pressure. Now, NJ City is planning to build a new transportation hub to ease the pressure. NJ City contains $n$ districts, and some pairs of districts are connected by bidirectional trunk roads. The new transportation hub will be built on top of these trunk roads by upgrading some of them into new-type trunk roads. After the upgrade, a trunk road can bear dozens of times more pressure than before. For balanced development, once the new transportation hub is completed, any two districts must be connected using only new-type trunk roads (directly or indirectly). The government has estimated the cost of upgrading each trunk road into a new-type trunk road. It wants to minimize the total cost of building the new hub and solicits plans from citizens with a massive bonus. The government soon realized that minimum-cost plans may not be unique, so it will divide the bonus equally among the first proposer of each distinct plan; that is, if someone proposes a plan with minimum cost and nobody before them proposed exactly the same plan, they will receive a share. Js08 is deeply attracted by the bonus and prepares to design a plan. However, he finds there may be many plans, and if there are too many winners, the share for each person will not be much. So he decides to first compute how many feasible plans there are.

The input has $m + 1$ lines. The first line contains two numbers $n, m$, representing how many districts the city has and how many trunk roads there are. The next $m$ lines each contain three numbers $a _ i$, $b _ i$, $c _ i$, indicating that there is a trunk road between district $a _ i$ and district $b _ i$, and upgrading it costs $c _ i$.

Output how many minimum-cost plans there are. Since the answer may be large, output the number modulo $31011$.

Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 100$, $1 \leq m \leq 1000$, $1 \leq a _ i, b _ i \leq n$, $1 \leq c _ i \leq 10 ^ 9$. Translated by ChatGPT 5