Jamie and Interesting Graph

Jamie는 최근 다음과 같은 성질을 가진 가중치가 있는 무방향 그래프를 매우 흥미롭게 여기게 되었다:

• 그래프는 연결되어 있으며 정확히 n개의 정점과 m개의 간선을 포함한다.
• 모든 간선의 가중치는 정수이며 $[1, 109]$ 범위에 양 끝값을 포함하여 속한다.
• 1에서 n까지의 최단 경로 길이는 소수이다.
• 그래프의 최소 스패닝 트리(MST)에 포함된 간선들의 가중치 합은 소수이다.
• 그래프에는 루프나 다중 간선이 없다.

문제에 나오는 일부 용어가 익숙하지 않다면 참고 절에서 그 정의를 확인할 수 있다.

Help Jamie 주어진 정점 수와 간선 수를 가지는 흥미로운 그래프를 아무거나 구성하라!

입력의 첫 번째 줄에는 필요한 정점 수와 간선 수를 나타내는 2개의 정수 n, m 가 주어진다.

첫 번째 줄에 최단 경로의 길이와 최소 스패닝 트리에 포함된 간선들의 가중치 합을 나타내는 2개의 정수 sp, mstw (1 ≤ sp, mstw ≤ 1014)를 출력한다.

다음 m개의 줄에 그래프의 간선들을 출력한다. 각 줄에 u와 v를 연결하며 가중치가 w인 간선을 나타내는 3개의 정수 u, v, w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 109)를 출력한다.

예제 1의 그래프: 최단 경로의 정점 순서: {1, 2, 3, 4}. MST 간선들은 별표(*)로 표시되어 있다.

문제에서 사용된 용어의 정의:

무방향 그래프에서 최단 경로란 vi이 vi + 1에 인접하고 1 ≤ i < k이며, w(i, j)가 i와 j 사이의 간선 가중치일 때 가중치 합 이 최소가 되는 정점들의 순서열 (v1, v2, ... , vk)이다. (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