Problem Description

After successfully breaking through Lord lsp’s defenses, lqr and the group arrived beneath Lord lsp’s castle.

After Lord lsp turned evil, although he gained powerful superpowers and could use telekinesis to create buildings, his intelligence did not increase much.

Now lqr has figured out that the dark castle has $N$ rooms, $M$ bidirectional passages that can be built, and the length of each passage.

lqr knows Lord lsp well. To avoid having to think about the shortest path between two rooms every time, Lord lsp will surely build the castle as a tree.

However, to improve his moving efficiency as much as possible, Lord lsp will make the castle satisfy the following condition:

Let $D[i]$ be the shortest path length from room $i$ to room $1$ if all passages are built, and let $S[i]$ be the path length from room $i$ to room $1$ in the actually built tree-shaped castle. The requirement is that for all integers $i$, $S[i]=D[i]$ holds.

To defeat Lord lsp, lqr wants to know how many different castle construction plans there are.

It is guaranteed that at least one feasible castle construction plan exists.

You need to output the answer modulo $2^{31}–1$.

Input Format

The first line contains two integers $N$ and $M$.

The next $M$ lines each contain three integers $X$, $Y$, and $L$, indicating that a passage of length $L$ can be built between $X$ and $Y$.

Output Format

Output one integer, the answer modulo $2^{31}–1$.

3 3
1 2 2
1 3 1
2 3 1

2

Hint

Constraints: $2 \le N \le 1000$, $N-1 \le M \le N(N-1)/2$, $1 \le L \le 100$.

Translated by ChatGPT 5