One Pass Short

Jigui implemented the Bellman-Ford algorithm to decide whether a directed graph whose edge weights are all $1$ or $-1$ has a negative cycle.

1. Set $d[v] = 0$ for every vertex $v$.
2. One round scans every edge $(s, e, w)$ in the order given in the input and assigns $\min(d[e],\ d[s] + w)$ to $d[e]$. Each edge changes $d$ right away, so the next edge of the same round reads the changed values.
3. Repeat the round $N - 2$ times. It should have been $N - 1$ times.
4. Run one more round. If any value of $d$ changes during that round, report that a negative cycle exists.

Because step 3 runs one round too few, the code reports a negative cycle on a graph that has none. Build such a graph yourself and show that Jigui's code is wrong.

You are given the number of vertices $N$. Print a directed graph on $N$ vertices whose edge weights are all $1$ or $-1$, that has no negative cycle, and that the code above declares to have one. The order in which you print the edges is the order in which the code scans them, so the order is part of the answer.

Many graphs satisfy the conditions. Print the one with the smallest number of edges $M$. If several graphs remain, lay the printed edges out as the sequence $s_1, e_1, d_1, s_2, e_2, d_2, \dots, s_M, e_M, d_M$, compare the sequences number by number, and print the one that comes first.

The first line contains the number of vertices $N$. ($50 \le N \le 100$)

On the first line print the number of vertices $N$ and the number of edges $M$. ($0 \le M \le N \times (N - 1)$)

On each of the next $M$ lines print the start vertex $s$, the end vertex $e$, and the weight $d$ of one edge. ($1 \le s, e \le N$, $s \ne e$, $d = 1$ or $d = -1$)

Do not print the same pair $(s, e)$ twice.