Misimplemented Dinic

Jigui always solves flow problems with the Edmond-Karp algorithm. One day Jigui saw a flow problem with 500 vertices and 100000 edges. Jigui built a flow graph, wrote about 2000 bytes of code, and submitted it, but the submission was not accepted. Tired of tuning the code, Jigui found Dinic's algorithm, whose worst-case time complexity is $O(V^2 E)$.

Dinic's algorithm is as follows.

1. Treat every residual edge as an edge of length 1 and compute the shortest-path distance $d_v$ from the source to every vertex.
2. Find an augmenting path with DFS and push flow. Push flow on an edge $u \to v$ only when $d_u + 1 = d_v$.
3. Repeat steps 1 and 2 until no more flow can be pushed.

The $O(V^2 E)$ bound is justified as follows.

1. Steps 1 and 2 run at most $O(V)$ times. Each run increases $d_{\mathrm{sink}}$ by at least 1, and $d_{\mathrm{sink}}$ cannot exceed $V$.
2. Step 1 is $O(E)$. It can be computed with BFS.
3. Step 2 is $O(VE)$. Each time flow is pushed, at least one edge becomes saturated, so there are at most $O(E)$ augmenting paths. Each augmenting path has length at most $V$.

Jigui implemented the algorithm carefully and still did not get an accepted verdict. Dotori looked at the code and pointed out a small mistake: when the search for an augmenting path starts, edges that cannot carry more flow are scanned from the beginning of the adjacency list every time. Jigui will not believe this until a small example graph is shown.

Help Dotori print that example graph. The graph to print is unique.

The problem Jigui is solving sends flow from vertex 1 to vertex $N$. Edges are stored in a linked list, and a new edge is inserted at the front of the list, so a later input edge is used first.

There is no input.

Print the number of vertices $N$ and the number of edges $M$ on the first line. $N$ is $4$ and $M$ is $5$.

Then print $M$ lines, each with a start vertex $s$, an end vertex $e$, and a capacity $f$, in this order:

• from $1$ to $2$ with capacity $3$
• from $1$ to $3$ with capacity $4$
• from $1$ to $4$ with capacity $5$
• from $2$ to $4$ with capacity $2$
• from $3$ to $4$ with capacity $2$

The graph has no duplicate edges. Each line prints the integers $s$, $e$, and $f$ in that order, separated by spaces.