题目描述
一座枢纽站网络共 $n$ 个站点，拟修建 $m$ 条候选双向管线，每条连接两个站点、有一个耗时。 最终修建的管网必须是树形（连通且恰含 $n-1$ 条管线）。记 $D_i$ 为全修时站点 $i$ 到枢纽站 $1$ 的最短耗时， $S_i$ 为最终树形管网中站点 $i$ 到站 $1$ 的路径耗时。要求对所有 $i$ 都有 $S_i = D_i$。 求满足条件的不同修建方案数，对 $2^{31} - 1$ 取模。
输入格式
第一行两个整数 $n, m$。 接下来 $m$ 行每行三个整数 $x, y, l$：一条候选管线两端点与耗时。
输出格式
一行一个整数：方案数对 $2^{31}-1$ 取模的结果。
数据范围
None