Dark Castle Spanning Trees

After breaking through Lord lsp's defenses, lqr and his team arrived at the base of Lord lsp's castle. Although Lord lsp, after turning evil, has acquired formidable superpowers, including the ability to construct buildings using telekinesis, his IQ has not improved much.

The dark castle contains \(N\) rooms and \(M\) bidirectional potential corridors, each with an associated length. Knowing Lord lsp’s intentions, lqr discovered that the castle is always built as a tree. Moreover, to maximize his own mobility, Lord lsp will ensure the castle satisfies the following condition:

Let \(D[i]\) denote the shortest distance from room \(1\) to room \(i\) when all \(M\) corridors are considered, and let \(S[i]\) denote the distance from room \(1\) to room \(i\) in the actual tree built. It is required that for every room \(i\), \(S[i] = D[i]\) holds.

In order to defeat Lord lsp, lqr wants to know how many different castle construction schemes (i.e. spanning trees) exist that satisfy the above property. Since the answer can be very large, output it modulo \(2^{31}-1\) (i.e. modulo 2147483647).

Note: There is a guarantee that at least one valid construction scheme exists.

inputFormat

The input begins with two integers \(N\) and \(M\) \((1 \leq N \leq \text{some limit},\ N-1 \leq M \leq \text{some limit})\), representing the number of rooms and potential corridors, respectively. Each of the following \(M\) lines contains three integers \(u\), \(v\), and \(w\) indicating that there is a bidirectional corridor connecting room \(u\) and room \(v\) with length \(w\).

You may assume that the graph is connected and that there is at least one valid spanning tree satisfying the condition.

outputFormat

Output a single integer, the number of valid spanning tree construction schemes modulo \(2^{31}-1\) (i.e. modulo 2147483647).

sample

3 3
1 2 1
1 3 2
2 3 1

2