School Tour

Gukhee guides high school students around the campus during the summer vacation. The campus is on a hillside, so a road between two buildings is either an uphill road or a downhill road. Gukhee surveyed every road once, taking the entrance as the starting point.

The buildings are numbered $1$ through $N$, and the entrance is numbered $0$. Exactly one road leaves the entrance, and it leads to building $1$.

To introduce every building, Gukhee has to choose a set of roads that connects the entrance and all $N$ buildings, and she chooses as few roads as possible. There are $N+1$ places in total, so she chooses exactly $N$ roads, and those $N$ roads alone must let her reach every building from the entrance.

The fatigue of a choice is $k^2$, where $k$ is the number of uphill roads among the chosen roads. Uphill and downhill come from the original survey only, so walking down a downhill road and climbing back up it later is not counted. The road between the entrance and building $1$ belongs to every choice, so it counts as well.

Among all valid choices, one has the largest fatigue and one has the smallest. Find the difference between the two.

The first line has the number of buildings $N$ ($1 \le N \le 1000$) and the number of roads between buildings $M$ ($1 \le M \le N(N-1)/2$).

The second line describes the road between the entrance and building $1$ in the form $A$ $B$ $C$. Here $A$ is always $0$ and $B$ is always $1$.

Each of the next $M$ lines has $A$ $B$ $C$, meaning that a road joins building $A$ and building $B$ ($1 \le A, B \le N$, $A \ne B$). $C$ is $0$ for an uphill road and $1$ for a downhill road.

No pair of buildings is joined by more than one road. Every building is reachable from the entrance.

Print the difference between the largest fatigue and the smallest fatigue on one line.