// Single-room scheduling for a set of intervals.
// Processes interval endpoints with left-to-right sweep
// looking for overlap and then discards overlapping
// interval with latest right endpoint.  (Not the 2320 notes 06 greedy alg.
// for activity scheduling)
// BPW 09/24/08 (from maxKcolorHeap.java)

import java.util.Scanner;
import java.util.Arrays;

public class oneRoom
{
  public static class oneRoomFails extends Exception
  {
    public oneRoomFails()
    {
      super();
    }

    public oneRoomFails(String message)
    {
      super(message);
    }
  }

  static int k,n;    // # of colors (must be 1), # of intervals

  // Input intervals.
  static public class intervalType implements Comparable<intervalType>
  {
    int left;            // beginning
    int right;           // ending
    int color;           // 0 means interval has been rejected

    public int compareTo(intervalType other)
    {
      return this.right - other.right;
    }
  }

  static intervalType[] interval;

  static class endpointType implements Comparable<endpointType>
  {
    int sub;           // Subscript of interval for this endpoint
    boolean leftFlag;  // Set for interval beginnings

    public int compareTo(endpointType other)
    {
      int result;

      result=(this.leftFlag?interval[this.sub].left:interval[this.sub].right)
        - (other.leftFlag?interval[other.sub].left:interval[other.sub].right);
      if (result!=0)
        return result;

      // Force right ends to be processed before left ends when
      // duplicate endpoints occur.
      return (this.leftFlag ? 1:0) - (other.leftFlag ? 1:0);
    }
  }

  static endpointType[] endpoint;

  public static void main(String[] args) throws oneRoomFails
  {
    int i,j,intervalsColored=0;

    Scanner sc=new Scanner(System.in);
    k=sc.nextInt();
    n=sc.nextInt();

    if (k!=1)
      throw new oneRoomFails("Fatal - k is not 1");

    interval=new intervalType[n];
    for (i=0;i<n;i++)
      interval[i]=new intervalType();
    endpoint=new endpointType[2*n];
    for (i=0;i<2*n;i++)
      endpoint[i]=new endpointType();

    // Get input intervals.
    for (i=0;i<n;i++)
    {
      interval[i].left=sc.nextInt();
      interval[i].right=sc.nextInt();
      if (interval[i].left>=interval[i].right)
        throw new oneRoomFails("Bad input");
    }

    // Sort intervals based on their ending times.
    Arrays.sort(interval);

    // Prepare endpoints for sweep
    for (i=0;i<n;i++)
    {
      endpoint[2*i].sub=i;
      endpoint[2*i].leftFlag=true;
      endpoint[2*i+1].sub=i;
      endpoint[2*i+1].leftFlag=false;
    }
    Arrays.sort(endpoint);

    intervalType currentInterval=null;

    // Sweep to prevent overlap of intervals in final schedule.
    for (i=0;i<2*n;i++)
      if (endpoint[i].leftFlag)
        if (currentInterval==null)
        {
          intervalsColored++;
          currentInterval=interval[endpoint[i].sub];
          currentInterval.color=1;
        }
        else if (currentInterval.right>interval[endpoint[i].sub].right)
        { // Reject currentInterval
          currentInterval.color=0;
          currentInterval=interval[endpoint[i].sub];
          currentInterval.color=1;
        }
        else // Reject input interval
          interval[endpoint[i].sub].color=0;
      else // Right end of interval
        if (interval[endpoint[i].sub].color==1)
        {
          if (currentInterval!=interval[endpoint[i].sub])
            throw new oneRoomFails("Fatal - current interval is wrong");
          currentInterval=null;
        }
    if (currentInterval!=null)
      throw new oneRoomFails("Fatal - current interval at termination");

    System.out.format("%d %d %d\n",k,n,intervalsColored);
    for (i=0;i<n;i++)
      System.out.format("%d %d %d\n",interval[i].left,interval[i].right,
        interval[i].color);
  }

}