Jamie 最近发现无向加权图具有以下非常有趣的属性:
- 该图是连通的并且恰好包含 n 个顶点和 m 个边。
- 所有边权重均为整数,且在 [1, 109] 范围内(含)。
- 从 1 到 n 的最短路径的长度是一个素数。
- 图的最小生成树 (MST) 中边的权重之和是素数。
- 该图不包含循环或多边。
如果您不熟悉声明中的某些术语,您可以在注释部分找到它们的定义。
帮助 Jamie 构建任何具有给定数量的顶点和边的有趣图表!
输入
输入的第一行包含 2 个整数 n, m $$( 2 \leq n \leq 10^{5}, n - 1 \leq m \leq min ( \frac { n ( n - 1 ) } { 2 }, 1 0 ^ { 5 } ) )$$ — 所需的顶点和边数。
输出
第一行输出 2 个整数 sp, mstw (1 ≤ sp, mstw ≤ 1014) — 最短路径的长度以及最小生成树中边的权重之和。
在接下来的 m 行中输出图形的边缘。每行输出 3 个整数 u、v、w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 109),描述连接 u 和 v 且权重为 w 的边。
示例
输入 #1
4 4
输出 #1
7 7 1 2 3 2 3 2 3 4 2 2 4 4
输入 #2
5 4
输出 #2
7 13 1 2 2 1 3 4 1 4 3 4 5 4
注意
样本1的图:最短路径序列:{1,2,3,4}。 MST 边缘标有星号 (*)。
问题陈述中使用的术语定义:
无向图中的最短路径是一系列顶点 (v1, v2, ... , vk),使得 vi 与 vi + 1 1 ≤ i < k 相邻,并且权重 $$\sum_{i=1}^{n-1} w(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