Description

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

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

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

就给他个教训吧！

Input Format

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

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

Output Format

输出几行以以下格式描述简单无向图的输入数据，使得 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$ 个顶点。

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

1

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

Hint

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

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

翻译来自于：ChatGPT。