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_!
## Input
First line of input contains 2 integers _n_, _m_ — the required number of vertices and edges.
## Output
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_.
[samples]
## Note
**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](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](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/Minimum_spanning_tree))
[https://en.wikipedia.org/wiki/Multiple_edges](https://en.wikipedia.org/wiki/Multiple_edges)
Jamie 最近发现具有以下性质的无向加权图非常_有趣_：
如果你不熟悉题面中的某些术语，可以在注释部分查找它们的定义。
帮助 Jamie 构造一个具有给定顶点数和边数的_有趣_图！
输入的第一行包含 2 个整数 #cf_span[n], #cf_span[m] —— 所需的顶点数和边数。
第一行输出 2 个整数 #cf_span[sp], #cf_span[mstw] #cf_span[(1 ≤ sp, mstw ≤ 1014)] —— 最短路径长度和最小生成树的边权总和。
接下来的 #cf_span[m] 行输出图的边。每行输出 3 个整数 #cf_span[u], #cf_span[v], #cf_span[w] #cf_span[(1 ≤ u, v ≤ n, 1 ≤ w ≤ 109)]，描述连接 #cf_span[u] 和 #cf_span[v] 且权重为 #cf_span[w] 的边。
*样例 1 的图：* 最短路径序列：#cf_span[{1, 2, 3, 4}]。MST 边用星号 (*) 标记。
*题面中使用的术语定义：*
无向图中的 *最短路径* 是一个顶点序列 #cf_span[(v1, v2, ... , vk)]，满足 #cf_span[vi] 与 #cf_span[vi + 1] 相邻（#cf_span[1 ≤ i < k]），且权重和最小，其中 #cf_span[w(i, j)] 是顶点 #cf_span[i] 和 #cf_span[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
## Input
输入的第一行包含 2 个整数 #cf_span[n], #cf_span[m] —— 所需的顶点数和边数。
## Output
第一行输出 2 个整数 #cf_span[sp], #cf_span[mstw] #cf_span[(1 ≤ sp, mstw ≤ 1014)] —— 最短路径长度和最小生成树的边权总和。接下来的 #cf_span[m] 行输出图的边。每行输出 3 个整数 #cf_span[u], #cf_span[v], #cf_span[w] #cf_span[(1 ≤ u, v ≤ n, 1 ≤ w ≤ 109)]，描述连接 #cf_span[u] 和 #cf_span[v] 且权重为 #cf_span[w] 的边。
[samples]
## Note
*样例 1 的图：* 最短路径序列：#cf_span[{1, 2, 3, 4}]。MST 边用星号 (*) 标记。
*题面中使用的术语定义：*
无向图中的 *最短路径* 是一个顶点序列 #cf_span[(v1, v2, ... , vk)]，满足 #cf_span[vi] 与 #cf_span[vi + 1] 相邻（#cf_span[1 ≤ i < k]），且权重和最小，其中 #cf_span[w(i, j)] 是顶点 #cf_span[i] 和 #cf_span[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
Given:
- $ n $: number of vertices, $ m $: number of edges.
Define:
- $ \text{sp} $: length of the shortest path between some pair of vertices.
- $ \text{mstw} $: total weight of the minimum spanning tree (MST).
Constraints:
- $ 1 \leq n, m \leq 10^5 $ (implied by input bounds), $ 1 \leq \text{sp}, \text{mstw} \leq 10^{14} $, edge weights $ 1 \leq w \leq 10^9 $.
- Graph is undirected, weighted, simple (no multiple edges or self-loops implied by standard interpretation).
- Graph must be connected (to have a spanning tree and finite shortest paths).
Objective:
Construct a connected undirected weighted graph with $ n $ vertices and $ m $ edges such that:
- The shortest path between some pair of vertices has length $ \text{sp} $.
- The total weight of the MST is $ \text{mstw} $.
Construction:
Let vertices be labeled $ 1, 2, \dots, n $.
1. **MST Construction**:
- Use a star topology: connect vertex $ 1 $ to all other vertices $ 2, 3, \dots, n $.
- Assign weight $ w_i = \frac{\text{mstw}}{n-1} $ to each edge $ (1, i) $ for $ i = 2, \dots, n $.
- *Ensure $ \text{mstw} $ is divisible by $ n-1 $*; if not, adjust weights slightly to preserve total $ \text{mstw} $ and keep all weights $ \geq 1 $.
- For simplicity, set:
$$
w_i = \left\lfloor \frac{\text{mstw}}{n-1} \right\rfloor \quad \text{for } i = 2, \dots, n-1, \quad w_n = \text{mstw} - (n-2) \cdot \left\lfloor \frac{\text{mstw}}{n-1} \right\rfloor
$$
Ensure $ w_n \geq 1 $ and all weights $ \leq 10^9 $. If not possible, use a path graph instead (see below).
2. **Shortest Path Construction**:
- To achieve shortest path $ \text{sp} $, create a path $ 1 \to 2 \to \dots \to k $ of length $ \text{sp} $.
- Set edge weights along this path to 1, and ensure the path has exactly $ \text{sp} $ total weight.
- Thus, use a path of $ \text{sp} + 1 $ vertices: $ v_1 = 1, v_2 = 2, \dots, v_{\text{sp}+1} = \text{sp}+1 $, with each edge $ (i, i+1) $ having weight 1.
- Total path weight = $ \text{sp} $.
3. **Combine**:
- Use the path $ 1 - 2 - \dots - (\text{sp}+1) $ with unit weights.
- Connect remaining vertices $ \text{sp}+2, \dots, n $ to vertex $ 1 $ with weights chosen to sum to $ \text{mstw} - \text{sp} $.
- Total MST edges: $ (1,2), (2,3), \dots, (\text{sp}, \text{sp}+1) $ — $ \text{sp} $ edges of weight 1 — plus $ (1, j) $ for $ j = \text{sp}+2, \dots, n $ — total $ n-1 $ edges.
- MST weight = $ \text{sp} + \sum_{j=\text{sp}+2}^n w_{1j} = \text{mstw} $ → so set $ \sum_{j=\text{sp}+2}^n w_{1j} = \text{mstw} - \text{sp} $.
- Assign:
$$
w_{1j} = \left\lfloor \frac{\text{mstw} - \text{sp}}{n - \text{sp} - 1} \right\rfloor \quad \text{for } j = \text{sp}+2, \dots, n-1, \quad w_{1n} = (\text{mstw} - \text{sp}) - (n - \text{sp} - 2) \cdot \left\lfloor \frac{\text{mstw} - \text{sp}}{n - \text{sp} - 1} \right\rfloor
$$
Require $ \text{mstw} \geq \text{sp} $, $ n > \text{sp} $, and all weights $ \in [1, 10^9] $.
4. **Add Extra Edges**:
- We have used $ n-1 $ edges for MST. Need $ m - (n-1) $ additional edges.
- Add edges between non-adjacent vertices on the path (e.g., $ (1,3), (1,4), \dots $) with large weights (e.g., $ 10^9 $) to avoid affecting MST or shortest path.
- Ensure no edge weight exceeds $ 10^9 $.
Final Conditions:
- $ \text{sp} \leq n-1 $ (path cannot be longer than $ n-1 $ edges).
- $ \text{mstw} \geq \text{sp} $ (MST must include the path).
- $ m \geq n-1 $ (graph must be connected).
- All weights $ \in [1, 10^9] $.
Output:
- First line: $ \text{sp}, \text{mstw} $
- Next $ m $ lines: edges as constructed.
**Note**: If constraints cannot be satisfied (e.g., $ \text{mstw} < \text{sp} $, or $ \text{sp} \geq n $, or weights exceed $ 10^9 $), the problem guarantees a solution exists under input bounds, so assume valid inputs.
Formal Output:
$$
\boxed{
\begin{aligned}
&\text{sp}, \text{mstw} \\
&\text{For } i = 1 \text{ to } \text{sp}: \quad (i, i+1, 1) \\
&\text{For } j = \text{sp}+2 \text{ to } n: \quad (1, j, w_j) \quad \text{where } \sum_{j=\text{sp}+2}^n w_j = \text{mstw} - \text{sp}, \; w_j \in [1, 10^9] \\
&\text{For } k = 1 \text{ to } m - (n-1): \quad (u_k, v_k, 10^9) \quad \text{with } u_k, v_k \text{ non-adjacent, not in MST}
\end{aligned}
}
$$