D - 所有路径长度各不相同

得分：700分

问题描述

给定一个整数 $L$。构建一个满足以下条件的有向图。图中可能包含同一对顶点之间的多条边。可以证明这样的图一定存在。

• 顶点的数量 $N$ 最多为 20。顶点的ID编号为 1 到 N。
• 边的数量 $M$ 最多为 60。每条边的长度为 0 到 $10^6$（包括两端点）之间的整数。
• 每条边的方向都从较小的ID顶点指向较大的ID顶点。也就是说，1，2，...，N是顶点的一个可能的拓扑顺序。
• 从顶点 1 到顶点 N 一共有 $L$ 条不同的路径。这些路径的长度各不相同，且长度在 0 到 $L-1$ 之间的整数。

这里，路径的长度是路径中包含的边长度之和，当路径中包含的边的集合不同时，认为两条路径是不同的。

约束

• $2 \leq L \leq 10^6$
• $L$ 是一个整数。

输入

从标准输入获得数据，格式如下：

$L$

输出

在第一行，输出你的图中的顶点数和边数 $N$ 和 $M$。 在接下来的 $M$ 行中，输出第 $i$ 条边的起始顶点、终止顶点和边的长度的三个整数 $u_i,v_i$ 和 $w_i$。 如果有多个解，任何一个都可接受。

4

8 10
1 2 0
2 3 0
3 4 0
1 5 0
2 6 0
3 7 0
4 8 0
5 6 1
6 7 1
7 8 1

在样例输出所表示的图中，有四条从顶点1到顶点 $N=8$ 的路径：

• $1$ → $2$ → $3$ → $4$ → $8$ 长度为 $0$
• $1$ → $2$ → $3$ → $7$ → $8$ 长度为 $1$
• $1$ → $2$ → $6$ → $7$ → $8$ 长度为 $2$
• $1$ → $5$ → $6$ → $7$ → $8$ 长度为 $3$

其他解也是可行的。

5

5 7
1 2 0
2 3 1
3 4 0
4 5 0
2 4 0
1 3 3
3 5 1