SPFA Counter Challenge

BaoBao recently learned the SPFA (Bellman–Ford–Moore) algorithm and noticed its similarity to Dijkstra's algorithm when replacing the FIFO queue with a priority queue. In his modified version, when selecting a vertex from the queue Q, he always picks the vertex with the smallest priority value and in case of ties, the one with the largest index.

He claims his algorithm always works well. However, you know that on a carefully constructed simple undirected graph (i.e. no self‐loops or multiple edges) his algorithm may perform very slowly. In particular, you need to construct a graph such that when running the SPFA starting from vertex 1, the number of relaxations (tracked in a variable cnt) becomes no less than a given integer \(k\) at some time.

Your task is to output any simple undirected graph meeting the following requirements:

• The source vertex is fixed as vertex 1.
• The graph is simple (no self-loops or multiple edges) and undirected. An undirected edge between \(u\) and \(v\) is considered as two directed edges \((u,v)\) and \((v,u)\) with the same weight.
• When the SPFA is executed on your graph (without early termination for negative cycles), there exists a moment during the execution when the relaxation counter cnt reaches at least \(k\).

Hint: A common way to force many relaxations in SPFA is to create a negative cycle that is reachable from the source. For example, if there is a cycle whose total edge weight is negative, then each traversal of the cycle can continuously decrease the distances and increase cnt. However, take care that the graph must be simple. (Note that since the graph is undirected, an edge \((u,v)\) appears only once in the input.)

Problem Construction:

You are given an integer \(k\) in the input. You must output a graph in the following format:

1. The first line contains two integers \(n\) and \(m\) representing the number of vertices and the number of edges respectively.
2. Then \(m\) lines follow, each containing three integers \(u\), \(v\) and \(w\) which denote an undirected edge between vertices \(u\) and \(v\) with weight \(w\). The weight can be negative.

Construction Strategy:

One valid strategy is as follows:

• If \(k = 1\): Output a graph with \(n = 2\) and one edge \(1 \; 2\) with weight \(-1\). Then, when SPFA starts from vertex 1, it relaxes the edge \((1,2)\) and later, when processing vertex 2, relaxes \((2,1)\) (since the edge is undirected) so that the counter increases indefinitely.
• If \(k \ge 2\): Output a graph with \(n = k+1\) vertices and \(m = k+1\) edges. For \(i = 1,2,\dots,k\), output a chain edge from \(i\) to \(i+1\) with weight 0. Then add an extra edge between vertex 1 and vertex \(k+1\) with weight \(-1\). This extra edge creates a negative cycle:
  \(1 \to 2 \to \cdots \to k+1 \to 1\) with total weight \(0 + \cdots + 0 + (-1) = -1\). As SPFA repeatedly relaxes this cycle, the counter cnt will eventually reach \(k\).

You may output any graph satisfying the requirements.

inputFormat

The input consists of a single integer \(k\) (\(1 \le k \le 10^5\)) on one line.

outputFormat

Output a simple undirected weighted graph in the following format:

1. The first line contains two integers \(n\) and \(m\), the number of vertices and edges respectively.
2. Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\) representing an edge between vertices \(u\) and \(v\) with weight \(w\).

The graph must be constructed so that when running BaoBao’s SPFA algorithm from vertex 1, at some moment the relaxation counter cnt becomes at least \(k\).

sample

1

2 1
1 2 -1

</p>