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 翻译