好的，我将题目中的数字和名称用 $...$ 标出。

题目描述

知道黑暗城堡有 $N$ 个房间，$M$ 条可以建造的双向通道，以及每条通道的长度。

城堡是树形的并且满足下面的条件：

• 设 $D_i$ 为如果所有的通道都被修建（即全连通图），第 $i$ 号房间与第 $1$ 号房间的最短路径长度。
• 设 $S_i$ 为实际修建的树形城堡中第 $i$ 号房间与第 $1$ 号房间的路径长度。
• 要求对于所有整数 $i(1 \le i \le N)$，有 $S_i = D_i$ 成立。

你想知道有多少种不同的城堡修建方案（不同的生成树方案数，并且满足 $S_i = D_i$）。
输出答案对 $2^{31} - 1$ 取模之后的结果。

输入格式

第一行两个整数 $N,M$。
接下来 $M$ 行，每行三个整数 $x,y,l$，表示 $x$ 号房间与 $y$ 号房间之间的通道长度为 $l$。

输出格式

一个整数，表示不同的城堡修建方案数对 $2^{31} - 1$ 取模之后的结果。

数据范围

• $1 \le N \le 1000$
• $1 \le M \le \frac{N(N-1)}{2}$
• $1 \le l \le 200$

输入样例

4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1

输出样例

6

样例解释

有 $4$ 个房间，$6$ 条通道长度分别为：
$(1,2):1$, $(1,3):2$, $(1,4):3$, $(2,3):1$, $(2,4):2$, $(3,4):1$

先求所有通道都建时，从 $1$ 到各点的最短路径 $D_i$（用 Dijkstra 或 Floyd）：
$D_1 = 0$
$D_2 = 1$（直接 $1 \to 2$）
$D_3 = 2$（$1 \to 3$ 直接 2，或 $1 \to 2 \to 3$ 也是 $1+1=2$）
$D_4 = 2$（$1 \to 2 \to 4$ 为 $1+2=3$，但 $1 \to 3 \to 4$ 为 $2+1=3$，$1 \to 2 \to 3 \to 4$ 为 $1+1+1=3$，都不如 $1 \to 2 \to 4$ 更短？等一下，需要重新算）

用 Dijkstra 从 $1$ 出发：

• 到 $2$: $1$
• 到 $3$: $1+1=2$（经 $2$）或直接 $2$
• 到 $4$: 经 $3$：$2+1=3$，经 $2$：$1+2=3$，直接 $3$，所以 $D_4 = 3$。

但题目样例说明中 $D_4 = 3$，但它是 $3$ 吗？我们检查：
可能 $1 \to 2 \to 3 \to 4$ 是 $1+1+1=3$，确实最小是 $3$。
所以 $D = [0, 1, 2, 3]$。

现在要求生成树满足从 $1$ 到每个点的树上路径长度等于 $D_i$。

那么对于每个点 $i$（除 $1$ 外），它的父节点必须满足 $D[父] + 边权 = D[i]$。

枚举所有点 $i$，计算有多少个点 $j$ 满足 $D_j + w(j,i) = D_i$，那么 $i$ 的父节点可以是这些 $j$ 中的任意一个，方案数乘起来。

计算：

• $i=2$：$D_1 + w(1,2)=0+1=1=D_2$，$D_3 + w(3,2)=2+1=3 \neq 1$，只有 $1$ 一个父节点候选，方案数 $1$。
• $i=3$：$D_1 + w(1,3)=0+2=2=D_3$，$D_2 + w(2,3)=1+1=2=D_3$，有两个候选 $1$ 和 $2$，方案数 $2$。
• $i=4$：$D_1 + w(1,4)=0+3=3=D_4$，$D_2 + w(2,4)=1+2=3=D_4$，$D_3 + w(3,4)=2+1=3=D_4$，有三个候选 $1,2,3$，方案数 $3$。

总方案数 $= 1 \times 2 \times 3 = 6$。

输出 $6$。

这样题目就完整了，所有数字和名称都用 $...$ 标出。