eolymp
bolt
Try our new interface for solving problems
Problems

Hard Test

Hard Test

Time limit 1 second
Memory limit 128 MiB

Andrew is having a hard time preparing his 239^th contest for Petrozavodsk. This time the solution to the problem in based on Dijkstra algorithm and Andrew wants to prepare the hard test for the algorithm.

The Dijkstra algorithm is used to find the shortest path from a sourse vertex to all other vertices in a graph. The algoritm acts a foolows. Let G be a weight directed graph with vertex set V, edge set E and weight function w : ER^{+}. Let all vertices be reachable from vertex s. The algorithm used a set of vertices U, first initialized as empty. Each vertex is labeled with either an integer nomber, or with +∞. Inittialy all vertices are labeled with +∞, and the vertex s is labeked with 0. Denote the label of vertex v as d[v].

A step of the algorithm is the following: the vertex with the minimal label doesn't belong to U is selected. Let thes vertex be u. The vertex u is added to the set U, and each edge uvE is relaxed. The relaxation replesed d[v] with min(d[v], d[u] + w(uv)). The algorithm is over when all vertices belong to U. If the label of the vertex v has chenged, the relaxation in said to be active.

Now Andrew would like to create a graph with N vertices and M edges, such that the Dijkstra algorithm mskes as many active relaxations as possible. Help him to create such graph. To avoid nondeterminism, each time when selecting a vertex with minimal label among vertices that are not in U there must be exactly one vertex with the minimal label.

Input data

The firs line of the input file contains two integer numbers: N and M - the number of vertices and the number of edges in the graph Andrew would to create (4N1000, N-1MN^2/5).

Output data

Output M lines - the edges of the graph. Each line must contain three integer numbers: the beginning of the edge, the end of the edge and the weight of the edge. All weights must be non-negative and must not exceed 10^6. All vertices must be reachable from vertex 1.

If Dijkstra algorithm is run with s=1 there must be maximal possible number of active relaxations among all graphs with N vertices and M edges. There must be no loops and no parallel edges.

Examples

Input example #1
4 3
Output example #1
1 2 0
2 3 8
2 4 9
Input example #2
5 5
Output example #2
1 2 0
1 3 1
2 4 15
2 5 16
3 4 10
Author Andrew Stankevich