最近，BaoBao 学习了最短路径快速算法（SPFA，或更正式地称为 Bellman-Ford-Moore 算法）以高效地解决最短路径问题。他意识到该算法在将先进先出（FIFO）队列替换为优先队列后，看起来与 Dijkstra 算法非常相似，并向你展示了如下伪代码。

算法 1 最短路径快速算法

1: function Spfa(G, s)  ▷ G 是给定的图，s 是源顶点
2: Create vertex priority queue Q
3: for each vertex v in G do
4: dist[v] ← +∞  ▷ 从 s 到 v 的未知距离
5: vis[v] ← false  ▷ 开始时 Q 中没有顶点
6: end for
7: dist[s] ← 0  ▷ 初始化从 s 到 s 的距离为 0
8: Add s into Q with priority value 0
9: vis[s] ← true
10: cnt ← 0  ▷ 从优先队列中取出的次数
11: while Q is not empty do
12: Pick and remove best vertex u from Q  ▷ 解释如下
13: vis[u] ← false
14: cnt ← cnt + 1
15: for each neighbor v of u in G do
16: d ← dist[u] + wu,v  ▷ wu,v 是连接顶点 u 和 v 的边的权重
17: if dist[v] > d then
18: dist[v] ← d  ▷ 如果 d 更优，则更新 dist[v]
19: if vis[v] is false then
20: Add v into Q with priority value d
21: vis[v] ← true
22: end if
23: end if
24: end for
25: end while
26: end function

我们所说的从 $Q$ 中选取“最佳顶点”，是指选取优先级值最小的顶点（如果多个顶点具有相同的最小优先级值，则选取索引最大的那个）。

你，未来的计算机科学家，发现 BaoBao 修改后的 SPFA 算法在某些精心构造的图上运行得非常慢。然而，BaoBao 坚信他的算法运行良好，除非你能向他展示一个简单的无向图，使得 SPFA 函数中的变量 cnt 在某一时刻不小于某个 $k$。

给他点教训吧！

输入格式

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

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

输出格式

输出若干行，按照以下格式描述一个简单无向图的输入数据，使得 SPFA 函数中的变量 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

1

输出 1

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

说明

为了方便起见，你可以从比赛网站上复制与上述伪代码对应的 C++ 代码。将代码保存为 spfa.cpp，使用 g++ spfa.cpp -O2 -o spfa 进行编译，你将得到一个名为 spfa 的可执行文件。运行 spfa，将你的输出输入到其标准输入中，它将打印出 cnt 的最终值。根据样例输出，它将打印出 4，这意味着样例输出不足以通过秘密测试用例。

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