Description

You know that Dark Castle has $N$ rooms and $M$ possible bidirectional passages that can be constructed, along with the length of each passage.

The castle is tree-shaped and satisfies the following conditions:

Let $D_i$ be the shortest path length between the $i$-th room and the $1$-st room if all passages are built;

And let $S_i$ be the path length between the $i$-th room and the $1$-st room in the actually constructed tree-shaped castle;

It is required that for all integers $i$ ($1\le i\le N$), $S_i = D_i$ holds.

You want to know how many different castle construction schemes exist. Of course, you only need to output the result modulo $2^{31} -1$.

Input Format

The first line contains two integers separated by a space, $N$ and $M$;

The second to the $(M+1)$-th lines each contain three integers separated by spaces, $x$, $y$, $l$, indicating that the passage between the $x$-th room and the $y$-th room has a length of $l$.

Output Format

An integer: the number of different castle construction schemes modulo $2^{31} -1$.

Sample 1

There are $4$ rooms and $6$ passages, where the lengths of the passages between rooms 1 and 2, 1 and 3, 1 and 4, 2 and 3, 2 and 4, and 3 and 4 are $1$, $2$, $3$, $1$, $2$, and $1$, respectively.

The number of different castle construction schemes modulo $2^{31} -1$ is $6$.

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

6

Data Range and Hints

For all data, $1\le N\le 1000$, $1\le M\le \frac{N(N-1)}{2}$, $1\le l\le 200$.