← 返回题目列表

Codeforces · 916/C

C. 杰米和有趣的图表

中文机器翻译题面 查看原题

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