AT_xmascon23_d Distance Construction

正整数 $ M $ が与えられる．以下の条件をすべて満たす辺重み付き無向木が存在するか判定し，存在する場合は $ 1 $ つ作れ． - 頂点数 $ n $ は $ 2 \le n \le 10^3 $ を満たす． - 頂点集合は $ \{1, 2, \ldots, n\} $ である． - 各辺の重みは $ 1 $ 以上 $ M $ 未満の整数である． - 各 $ u = 1, 2, \ldots, n-1 $ に対し，頂点 $ u $ と頂点 $ u+1 $ の距離 (それらを結ぶ唯一の単純パスに含まれる辺の重みの和) は $ M $ の倍数である．

入力は以下の形式で標準入力から与えられる． > $ M $

条件を満たす辺重み付き無向木が存在する場合，そのようなもののうち $ 1 $ つを以下の形式で出力せよ： > $ 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 $ 点が与えられる． ### Constraints - $ 2 \le M \le 10^9 $ ．