Dijkstra's Nightmare (Easy)

Time limit: 1000 ms. Memory limit: 1024 MB.

Every computer scientist should be familiar with Dijkstra's algorithm, the basic algorithm for computing single-source shortest paths in a given graph. The algorithm maintains a set of active vertices. In each iteration, it selects and processes the active vertex with the smallest current distance. When processing a vertex, it examines the outgoing edges. If an edge can improve the distance to an adjacent vertex, the algorithm updates that distance and marks the adjacent vertex as active.

The algorithm is efficient when all edge lengths are non-negative. The reference implementation in this problem runs in $O(m \log n)$ time on such graphs, where $m$ is the number of edges and $n$ is the number of vertices.

Things get hairy once negative edge lengths are allowed. Finding the shortest simple path (a path with no repeated vertices) in such a graph is NP-hard. Some versions of Dijkstra's algorithm terminate quickly on such graphs but sometimes give incorrect results. The reference implementation does not, but it solves a slightly different problem: for each vertex $v$, it finds the length of the shortest walk from the starting vertex to $v$. A walk is a path that may repeat vertices and edges. If all edge lengths are positive, the shortest walk is always a simple path.

Sometimes no shortest walk from the starting vertex to some vertex $v$ exists, because for every walk there is an even shorter one. For such inputs the reference implementation never terminates.

In this problem, "graph" always means a directed weighted graph with no duplicate edges and no self-loops. $n$ and $m$ denote its numbers of vertices and edges. Vertices are numbered 0 through $n-1$. The starting vertex is 0.

We want you to show that there are graphs on which Dijkstra's algorithm terminates but its time complexity is exponential in the number of vertices. The reference implementation contains a variable named PROCESSED_VERTICES. Construct any valid graph (defined below) such that the implementation terminates after finitely many steps and the final value of PROCESSED_VERTICES is at least 10 000.

You are given the files d.cc and d.py. They contain equivalent reference implementations in C++11 and in Python 2.

In a valid graph, $1 ≤ n ≤ 60$ and the length of each edge fits into a signed 32-bit integer variable.

Each graph should be output as a sequence of $m + 2$ lines. The first line contains $n$, the second line contains $m$, and each of the following $m$ lines describes an edge with three integers: the numbers of its two endpoints (between 0 and $n-1$) followed by its length.

The output should contain exactly one such graph.