Best Edge

You are given a directed graph with $N$ vertices and $M$ edges. The edges are numbered from $1$ to $M$ in the order they appear in the input.

Soyeong thinks it is impressive when many pairs of vertices are connected by shortest paths. She gives each edge a score and awards the Best Edge prize to the edges with the highest score. An edge's score is computed as follows.

• If a shortest path exists from vertex $S$ to vertex $E$, every edge on that shortest path gets 1 point. The input only contains data where the shortest path is unique for every pair of vertices that has a path.
• If no path exists from $S$ to $E$, no edge gets a point for the pair $(S, E)$.
• The final score of an edge is the sum of its points over all pairs $(S, E)$ with $S \neq E$ and $1 \le S, E \le N$.

If several edges share the highest score, all of them receive the prize. Find the edges that receive the Best Edge prize.

The first line contains two integers $N$ and $M$, separated by a space. $(2 \le N \le 2 \times 10^3, 1 \le M \le \min(N \times (N-1), 5 \times 10^3))$

Each of the next $M$ lines contains the start vertex $u_i$, the end vertex $v_i$, and the length $w_i$ of the $i$-th edge, separated by spaces. No two edges connect the same pair of vertices, and no edge starts and ends at the same vertex. $(1 \le u_i, v_i \le N, u_i \neq v_i, 1 \le w_i \le 10^9)$

On the first line, print the number of edges that receive the prize. On the second line, print their numbers in increasing order, separated by spaces.