题目描述

Recently, BaoBao has learned the Shortest Path Fast Algorithm (SPFA, or more formally, Bellman-Ford-Moore Algorithm) to solve the shortest path problem efficiently. He realizes that the algorithm looks so similar to the Dijkstra's algorithm after replacing the FIFO queue with priority queue, and shows you the below pseudo code.

By picking the best vertex from $Q$ we mean picking the vertex with the smallest priority value (in case that multiple vertices have the smallest priority value, pick the vertex with the largest index among them).

You, the future computer scientist, find the BaoBao-modified SPFA algorithm works so slow in some carefully construted graph. However, BaoBao is sure that his algorithm works well, unless you show him a simple undirected graph that makes the variable $\tt{cnt}$ in the SPFA function no less than a certain $k$ $\textbf{at some time}$. For convenience, the source vertex of the SPFA function is specified to be vertex $1$.

Just teach him a lesson!

输入格式

There is only one test case in each test file.

The first and only line of the input contains a single integer $k$ where $k = 1$ for the sample test case and $k = 10^5$ for the only secret test case.

输出格式

Output several lines in the following format to describe the input data of a simple undirected graph that makes the variable $\tt{cnt}$ in the SPFA function no less than $k$ $\textbf{at some time}$.

The first line contains two integers $n$ ($1 \le n \le 100$) and $m$ ($0 \le m \le 10^3$), indicating the number of vertices and edges in the graph.

Then $m$ lines follow, the $i$-th of which contains three integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) and $w_i$ ($1 \le w_i \le 10^6$), indicating that the $i$-th edge in the graph has a weight of $w_i$ and connects the $u_i$-th and the $v_i$-th vertices.

Note that a simple graph contains no self-loops and no multiple edges.

题目大意

【题目描述】

最近，宝宝学习了最短路径快速算法（SPFA，或更正式地说，贝尔曼-福特-摩尔算法）以有效地解决最短路径问题。他意识到，如果用优先队列代替先进先出队列，该算法看起来与 Dijkstra 算法非常相似，并向你展示了下面的伪代码。

选择 $Q$ 中最佳顶点意味着选择具有最小优先级值的顶点（如果有多个顶点具有最小优先级值，则选择其中索引最大的顶点）。

作为未来的计算机科学家，你发现宝宝修改后的 SPFA 算法在某些精心构造的图中运行速度非常慢。然而，宝宝确信他的算法很好，除非你向他展示一个简单的无向图，在该图中，SPFA 函数中的变量 $\tt{cnt}$ 在某个时刻不少于某个 $k$。为方便起见，SPFA 函数的源顶点被指定为顶点 $1$。

就给他个教训吧！

【输入格式】

每个测试文件中只有一个测试用例。

输入的第一行包含一个整数 $k$，其中 $k = 1$ 为示例测试用例，$k = 10^5$ 为唯一的秘密测试用例。

【输出格式】

输出几行以以下格式描述简单无向图的输入数据，使得 SPFA 函数中的变量 $\tt{cnt}$ 在某个时刻不少于 $k$。

第一行包含两个整数 $n$（$1 \le n \le 100$）和 $m$（$0 \le m \le 10^3$），表示图中的顶点数和边数。

然后，跟着 $m$ 行，第 $i$ 行包含三个整数 $u_i$、$v_i$（$1 \le u_i, v_i \le n$）和 $w_i$（$1 \le w_i \le 10^6$），表示图中的第 $i$ 条边的权重为 $w_i$，连接了第 $u_i$ 个和第 $v_i$ 个顶点。

注意，简单图不包含自环和重边。

【提示说明】

为方便起见，你可以从比赛网站上复制与给定伪代码对应的 $\tt{C++}$ 代码。将代码保存为 $\tt{spfa.cpp}$，使用 $\text{g++ spfa.cpp -O2 -o spfa}$ 进行编译，你将得到一个名为 $\tt{spfa}$ 的可执行文件。运行 $\tt{spfa}$，将你的输出提供给它的标准输入，它将打印出 $\tt{cnt}$ 的 $\textbf{最终}$ 值。给出示例输出后，它将打印出 $4$，这意味着示例输出不足以通过秘密测试用例。

注意，给定的代码不会检查你的输出的有效性（例如，它不会检查你的输出是否真的是一个简单图）。即使可执行文件打印出一个很大的值，如果你的输出无效，你仍然可能失败测试。

翻译来自于：ChatGPT。

1

4 6
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
2 4 6

提示

For your convenience, you can copy the $\tt{C++}$ code, which corresponds to the given pseudo code, from the contest website. Save the code as $\tt{spfa.cpp}$, use $\text{g++ spfa.cpp -O2 -o spfa}$ to compile it and you will get an executable file named $\tt{spfa}$. Run $\tt{spfa}$, feed your output to its standard input and it will print out the $\textbf{final}$ value of $\tt{cnt}$. Given the sample output it will print out $4$, which means the sample output is not sufficient to pass the secret test case.

Note that the given code does not check the validity of your output (for example it does not check if your output is really a simple graph). You might still fail the test if your output is invalid, even if the executable prints out a large value.