Hard Test

Andrey Smit is preparing problems for a team olympiad. One of the problems is based on Dijkstra's algorithm, and A.S. wants to prepare a hard test for this algorithm.

Dijkstra's algorithm works as follows. Let G be a directed graph with vertex set V, edge set E, and weight function \textbf{w : E} \to \mathbf{R}^{+}. Assume all vertices are reachable from vertex s. The algorithm uses a set of vertices U, initially empty. Each vertex is marked by either an integer or by $+\infty$. Initially, all vertices are marked with $+\infty$, and vertex s is marked with $0$. Denote the label of vertex v as d_v.

A step of the algorithm is as follows: choose a vertex not in U with the minimal label. Let this vertex be u. Add u to U, and relax each edge uv \in \textbf{E}. Relaxation replaces d_v with \min(d_v, d_u + w(uv)). The algorithm ends when all vertices are added to U. If the label of vertex v changes, the relaxation is called active.

Now, Andrey Smit wants to build a graph with $N$ vertices and $M$ edges such that Dijkstra's algorithm performs the maximum possible number of active relaxations. Help him construct such a graph. To avoid non-determinism, assume that at every step there is exactly one vertex not in U with the minimal label.