AT_xmascon23_d.Distance Construction

给定一个正整数 $M$。判断是否存在满足下列所有条件的带权无向树，如果存在，请构造出其中一种。

• 顶点数 $n$ 满足 $2 \le n \le 10^3$。
• 顶点集合为 $\{1, 2, \ldots, n\}$。
• 每条边的权值是 $1$ 以上、小于 $M$ 的整数。
• 对于每个 $u = 1, 2, \ldots, n-1$，顶点 $u$ 到顶点 $u+1$ 的距离（它们之间唯一简单路径上的边权和）是 $M$ 的倍数。

输入为一行，包含一个整数 $M$。

如果存在满足条件的带权无向树，输出一种方案，格式如下：

$n$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ $\vdots$ $a_{n-1}$ $b_{n-1}$ $c_{n-1}$

$n$ 表示顶点数（$2 \le n \le 10^3$）。第 $i$ 条边（$1 \le i \le n-1$）连接顶点 $a_i$ 与 $b_i$（$1 \le a_i, b_i \le n$），权值为 $c_i$（$1 \le c_i < M$）。

如果不存在满足条件的带权无向树，则输出 -1。

部分分

• 对于 $M \le 10^2$ 的数据，答对将获得 $32$ 分。
• 对于无附加限制的数据，另有 $68$ 分。

约束条件

• $2 \le M \le 10^9$。

由 ChatGPT 5 翻译