CF916C.Jamie and Interesting Graph

Jamie has recently found undirected weighted graphs with the following properties very interesting:

• The graph is connected and contains exactly n vertices and m edges.
• All edge weights are integers and are in range [1, 109] inclusive.
• The length of shortest path from 1 to n is a prime number.
• The sum of edges' weights in the minimum spanning tree (MST) of the graph is a prime number.
• The graph contains no loops or multi-edges.

If you are not familiar with some terms from the statement you can find definitions of them in notes section.

Help Jamie construct any graph with given number of vertices and edges that is interesting!

杰米最近发现具有以下性质的无向带权图非常有趣：

• 该图是连通的，且恰好包含 $n$ 个顶点和 $m$ 条边；
• 所有边的权重均为整数，且取值范围为 $[1,\,10^9]$（含端点）；
• 从顶点 $1$ 到顶点 $n$ 的最短路径长度是一个质数；
• 该图的最小生成树（MST）中所有边的权重之和是一个质数；
• 该图不含自环或重边。

若你对题干中某些术语不熟悉，可参阅“注释”部分中的定义。

请帮助杰米构造一个满足给定顶点数和边数的“有趣”图！

First line of input contains 2 integers n, m — the required number of vertices and edges.

输入的第一行包含两个整数 $n$、$m$ —— 分别表示所需的顶点数和边数。

In the first line output 2 integers sp, mstw (1 ≤ sp, mstw ≤ 1014) — the length of the shortest path and the sum of edges' weights in the minimum spanning tree.

In the next m lines output the edges of the graph. In each line output 3 integers u, v, w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 109) describing the edge connecting u and v and having weight w.

第一行输出两个整数 $sp$、$mstw$（$1 ≤ sp, mstw ≤ 10^{14}$）—— 分别表示最短路径的长度和最小生成树中所有边的权重之和。

接下来 $m$ 行输出图的各条边。每行输出三个整数 $u$、$v$、$w$（$1 ≤ u, v ≤ n$，$1 ≤ w ≤ 10^9$），表示连接顶点 $u$ 和 $v$ 的一条权重为 $w$ 的边。

The graph of sample 1: Shortest path sequence: {1, 2, 3, 4}. MST edges are marked with an asterisk (*).

Definition of terms used in the problem statement:

A shortest path in an undirected graph is a sequence of vertices (_v_1, _v_2, ... , v__k) such that v__i is adjacent to v__i + 1 1 ≤ i < k and the sum of weight is minimized where w(i, j) is the edge weight between i and j. (https://en.wikipedia.org/wiki/Shortest_path_problem)

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. (https://en.wikipedia.org/wiki/Prime_number)

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. (https://en.wikipedia.org/wiki/Minimum_spanning_tree)

https://en.wikipedia.org/wiki/Multiple_edges

样例 1 的图：
最短路径序列：{1, 2, 3, 4}。最小生成树（MST）的边用星号（*）标记。

问题描述中所用术语的定义：

无向图中的最短路径是指一个顶点序列 (_v_1, _v_2, ... , v__k)，其中对任意满足 1 ≤ i < k 的 i，v__i 与 v__i + 1 相邻，且边权之和 最小，其中 w(i, j) 表示顶点 i 与 j 之间边的权重。（https://en.wikipedia.org/wiki/Shortest_path_problem）

质数是指大于 1 的自然数，且除了 1 和它自身之外没有其他正因数。（https://en.wikipedia.org/wiki/Prime_number）

最小生成树（MST）是指一个连通的、边带权的无向图中边的一个子集，该子集将所有顶点连接起来，不包含任何环，且具有可能的最小总边权。（https://en.wikipedia.org/wiki/Minimum_spanning_tree）

https://en.wikipedia.org/wiki/Multiple_edges