===== MST and Dijkstra =====



import java.util.*;

public class Solvers {

  
// ----------------------------------------------------------------------------
//            D I J K S T R A   N^2                                      
// ----------------------------------------------------------------------------
  
static void dijkstraNsquared(Graph g, int start,  final int [] dist, int [] pred ) {
  int INF = Integer.MAX_VALUE;
  int currnode = start, currdist, neigh;
  boolean [] closed = new boolean [g.N];

  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;

  for( int i = 0; i < g.N; i++ ){
    // find the closest node
    currdist = INF;
    for( int j = 0; j < g.N; j++)
      if( !closed[j] && dist[j] < currdist ){
        currdist = dist[j];
        currnode = j;
      }

    // expand the closest node and close it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
        dist[neigh] = dist[currnode] + g.w[currnode][j];
        pred[neigh] = currnode;
      }
     closed[currnode] = true;
    }
  } // for N steps
}

// ----------------------------------------------------------------------------
//            D I J K S T R A   E * log(N)                                     
// ----------------------------------------------------------------------------

public static void dijkstraElogN(Graph g, int start, final int [] dist, int [] pred ) {
  int currnode = start, currdist, neigh;
  int INF = Integer.MAX_VALUE;
  boolean [] closed = new boolean[g.N];

  PriorityQueue  pq
    = new PriorityQueue (g.N,
          new Comparator() {
            @Override
            public int compare(Integer n1, Integer n2) {
              if( dist[n1] < dist[n2] ) return -1;
              if( dist[n1] > dist[n2] ) return 1;
              return 0;
            }
          }
      );

  pq.add(start);
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;

  for(int i = 0; i < g.N; i++) {
    // current node is to be the nearest one, skip the closed nodes
    while( closed[currnode = pq.poll()] == true );
    // and expand current node
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > dist[currnode] + g.w[currnode][j]) ) {
        dist[neigh] = dist[currnode] + g.w[currnode][j];
        pred[neigh] = currnode;
        pq.add(neigh);
      }
     closed[currnode] = true;
    }
  }
}

// ----------------------------------------------------------------------------
//            M S T   P R I M    N^2                                      
// ----------------------------------------------------------------------------


static void MST_Nsquared(Graph g, int start,  final int [] dist, int [] pred ) {
  int INF = Integer.MAX_VALUE;
  int currnode = start, currdist, neigh;
  boolean [] closed = new boolean [g.N];

  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;

  for( int i = 0; i < g.N; i++ ){
    // find the closest node
    currdist = INF;
    for( int j = 0; j < g.N; j++)
      if( !closed[j] && dist[j] < currdist ){
        currdist = dist[j];
        currnode = j;
      }

    // expand the closest node and close it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
        dist[neigh] = g.w[currnode][j];
        pred[neigh] = currnode;
      }
     closed[currnode] = true;
    }
  } // for N steps
}


// ----------------------------------------------------------------------------
//            M S T   P R I M    E * log(N)                                       
// ----------------------------------------------------------------------------


public static void MST_ElogN(Graph g, int start, final int [] dist, int [] pred ) {
  int currnode = start, currdist, neigh;
  int INF = Integer.MAX_VALUE;
  boolean [] closed = new boolean[g.N];

  PriorityQueue  pq
    = new PriorityQueue (g.N,
          new Comparator() {
            @Override
            public int compare(Integer n1, Integer n2) {
              if( dist[n1] < dist[n2] ) return -1;
              if( dist[n1] > dist[n2] ) return 1;
              return 0;
            }
          }
      );

  pq.add(start);
  for(int i = 0; i < g.N; i++) pred[i] = i;
  Arrays.fill(dist, INF);
  Arrays.fill(closed, false);
  dist[start] = 0;

  for(int i = 0; i < g.N; i++) {
    // take the closest node
    while( closed[currnode = pq.poll()] == true );
    // and expand it
    for( int j = 0; j < g.dg[currnode]; j++ ){
      neigh = g.edge[currnode][j];
      if( !closed[neigh] && ( dist[neigh] > g.w[currnode][j]) ) {
        dist[neigh] = g.w[currnode][j];
        pred[neigh] = currnode;
        pq.add(neigh);
      }
     closed[currnode] = true;
    }
  }
}

// ----------------------------------------------------------------------------
//            M S T   K R U S K A L    E * alpha(N)                                       
// ----------------------------------------------------------------------------


public static void MST_Kruskal(Graph g, int [] edgesMST ) {

  // store edges in one arr and sort them
  int [] edges = new int[g.M*3];
  int k = 0;
  for( int i = 0; i < g.N; i++ )
    for( int j = 0; j < g.dg[i]; j++ ) {
      if( i <  g.edge[i][j] ) {
        edges[k++] = g.w[i][j];
        edges[k++] = i;
        edges[k++] = g.edge[i][j];
      }
    }
   qSort3( edges, 0, edges.length-3 );

   // construct the MST with UF
   UF_init( g.N );
   int edgesCount = 0, set1, set2;
   k = 0;
   while( edgesCount < g.N-1 ){
     set1 = UF_find(edges[k+1]); set2 = UF_find(edges[k+2]);
     if( set1 != set2 ) {  // found an edge of MST
       UF_union( set1, set2 );
       edgesCount++;
       edgesMST[edgesCount*2-2] = edges[k+1]; 
       edgesMST[edgesCount*2-1] = edges[k+2] ;
     }
     k += 3;
   }
}


// ----------------------------------------------------------------------------
//                   U N I O N  -  F I N D   
//      (also known as  "Disjoint-set data structure")
//        with path compression and  union by rank                                       
// ----------------------------------------------------------------------------

static int [] boss;
static int [] rank;

static void UF_init( int n ) {
	boss = new int [n];
	rank = new int [n];
  UF_reset();
}

static void UF_reset() {
  for( int i = 0; i < boss.length; i++ ) {
    boss[i] = i;  // fast copy from superboss;
    rank[i] = 0;
  }
}


static void UF_union( int a, int b ) {
  //System.out.printf(" unioning %d %d \n", a, b);
  if( rank[b] > rank[a] ) 
    boss[a] = b;
  else {
    boss[b] = a;
		if( rank[b] == rank[a] ) 
			rank[a]++;
  }
}

static int UF_find(int a) {
	return ( boss[a] == a ?  a  : ( boss[a] = UF_find( boss[a] ) ) );
}

/*
static int UF_find(int a) {  // an equivalent to UF_find one-liner
  int parent = boss[a];
  if( parent != a )
    boss[a] = UF_find(parent); 
  return boss[a];
}
*/

static void listSet(int a) {  // for debug purposes only
  int finda = UF_find(a);
  for(int i = 0; i < boss.length; i++)
    if(UF_find(i) == finda)
      System.out.printf("%d ", i);
  System.out.printf("\n");
}



// ----------------------------------------------------------------------------
//              U T I L I T I E S
// ----------------------------------------------------------------------------


static void list (int [] a) {
  for( int x : a )
    System.out.printf("%2d ", x);
  System.out.printf("\n");
}

static void qSort(double a[], int low, int high) {
  int iL = low, iR = high;
  double pivot = a[low];
  double aux;
  do {
    while (a[iL] < pivot) iL++;
    while (a[iR] > pivot) iR--;
    if (iL < iR) {
      //swap(a,iL, iR);
      aux = a[iL]; a[iL] = a[iR]; a[iR] = aux;
       iL++; iR--;
    }
    else
      if (iL == iR) { iL++; iR--;}

  } while( iL <= iR);

  if (low < iR)  qSort(a, low, iR);
  if (iL < high) qSort(a, iL, high);
}


// always points to i%3=0 elem which stores the key
static void qSort3(int a[], int low, int high) {
  int iL = low, iR = high;
  int pivot = a[low];
  int aux;
  do {
    while (a[iL] < pivot) iL+=3;
    while (a[iR] > pivot) iR-=3;
    if (iL < iR) {
      //swap(a,iL, iR);
      for(int k = 0; k < 3; k++ )
      { aux = a[iL+k]; a[iL+k] = a[iR+k]; a[iR+k] = aux; }
      iL+=3; iR-=3;
    }
    else
      if (iL == iR) { iL+=3; iR-=3;}

  } while( iL <= iR);

  if (low < iR)  qSort3(a, low, iR);
  if (iL < high) qSort3(a, iL, high);
}

// ----------------------------------------------------------------------------
//              M A I N 
// ----------------------------------------------------------------------------
  public static void main( String[] args ) {
    
  }

}

===== Weighted graph manipulation =====



import java.util.*;
import java.io.*;


public class Graph {

// ----------------------------------------------------------------------------
//                           M  A  I  N                                      
// ----------------------------------------------------------------------------


public static void main( String[] args ) {
  long t1, t2;
  
  // simple example
  Graph g = Graph.randomConnectedGraph(8, 12, 1, 10, 40112121 );
  g.setRandWeights(1, 15, 3488782 );
  g.print();

  t1 = System.currentTimeMillis();
  //Solvers.dijkstraNsquared(g, 0, g.dist, g.pred);
  //listEdgePred( g.pred );
  
  //Solvers.dijkstraElogN(g, 0, g.dist, g.pred);
  //listEdgePred( g.pred );
  
  //Solvers.MST_Nsquared(g, 2, g.dist, g.pred);
  //listEdgePred( g.pred );
  
  //Solvers.MST_ElogN(g, 2, g.dist, g.pred);
  //listEdgePred( g.pred );
  
  int [] edgesMST = new int[2*g.N-2];
  Solvers.MST_Kruskal(g, edgesMST);
  listEdgeArr( edgesMST );
  
   t2 = System.currentTimeMillis();
  System.out.printf("time %d\n", t2-t1);
 
}

// ------------------------- G R A P H   I T S E L F -------------------------- 

int N, M;       // # of nodes and edges
int [][] edge;  // graph itself, linked lists representation
int [][] w;     // edge weights
int [] dg;      // node degrees
int [] dist;    // node distances 
int [] pred;    // node predecessors in path/search 


// ----------------------------------------------------------------------------
//                           E S S E N T I A L S
// ----------------------------------------------------------------------------


// ------------------------- C O N S T R U C T O R ----------------------------  
// creates a graph with n nodes and no edges (so called empty graph) 

public Graph ( int n ) {
  N = n; M = 0;
  edge = new int [N][2]; 
  w = new int [N][2];
  dg = new int [N];
  dist = new int [N];
  pred = new int [N];
}

// ------------------------- A D D   E D G E  ---------------------------------
//          mainly for input reading or for a generator  

void addedge( int n1, int n2, int weight ) {

	// dynamically extend arrays if too short
  if( dg[n1] == edge[n1].length ){
    edge[n1] = Arrays.copyOf( edge[n1], dg[n1]*2 ); 
    w[n1] = Arrays.copyOf( w[n1], dg[n1]*2 );
  }
	if( dg[n2] == edge[n2].length ){
    edge[n2] = Arrays.copyOf( edge[n2], dg[n2]*2 );
    w[n2] = Arrays.copyOf( w[n2], dg[n2]*2 );
  }
  
  // add edge
	edge[n1][dg[n1]] = n2;
	edge[n2][dg[n2]] = n1;
	w[n1][dg[n1]++] = w[n2][dg[n2]++] = weight;
  M++;
}

// ---------------------------- P R I N T  ------------------------------------
//                     useful for debug purposes 

void print(){
  for( int node = 0; node < N; node++) {
    System.out.printf("%2d__", node  );
    for( int j_neigh = 0; j_neigh < dg[node]; j_neigh++ )
      System.out.printf( " %2d_%2d", edge[node][j_neigh], w[node][j_neigh] );
    System.out.printf("\n");
  }
  System.out.printf("-------------------- \n");
}

// -------------------------  L O A D -----------------------------------------

static Graph load( String fileName ) { try {
  BufferedReader br;
  if( fileName == null || fileName.isEmpty()  )
    br = new BufferedReader( new InputStreamReader( System.in ) );
  else
    br = new BufferedReader( new FileReader( fileName ) ) ;
  
  StringTokenizer st = new StringTokenizer( br.readLine() );
  int n = Integer.valueOf( st.nextToken() );
  int m = Integer.valueOf( st.nextToken() );

  Graph g = new Graph( n );

  int n1, n2, weight;
  for( int i = 0; i < m; i++ ){
    st = new StringTokenizer( br.readLine() );
    n1 = Integer.valueOf( st.nextToken() );
    n2 = Integer.valueOf( st.nextToken() );
    weight = Integer.valueOf( st.nextToken() );
    g.addedge( n1, n2, weight );
  }

  return g;
	}
	catch ( IOException ee ) { System.out.printf(  ee.getMessage()+"\n"  ); return null;}
}


// ----------------------------------------------------------------------------
//                           G E N E R A T O R S
// ----------------------------------------------------------------------------


// -------------------------  Kn ----------------------------------------------
 static Graph generate_Kn( int n ){
   Graph g = new Graph( n );
   for( int n1 = 0; n1 < n-1; n1++ )
     for( int n2 = n1+1; n2 < n; n2++ )
       g.addedge( n1, n2, 0 );
   return g;
 }


// -------------------------  Kn ----------------------------------------------
 static Graph generate_Kn( int n, int lo, int hi, int seed ){
   Graph g = new Graph( n );
     Random ra = new Random(seed);
   for( int n1 = 0; n1 < n-1; n1++ )
     for( int n2 = n1+1; n2 < n; n2++ )
       g.addedge( n1, n2, lo + ra.nextInt(hi-lo+1) );
   return g;
 }

// -------------------------  Kmn ---------------------------------------------
  static Graph generate_Kmn( int m, int n ){
   Graph g = new Graph( n+m );
   for( int n1 = 0; n1 < n; n1++ )
     for( int n2 = n; n2 < n+m; n2++ )
       g.addedge( n1, n2, 0 );
   return g;
 }

// -------------------------  Cn ----------------------------------------------  
  static Graph generate_Cn( int n ){
   Graph g = new Graph( n );
   for( int n1 = 0; n1 < n-1; n1++ )
       g.addedge( n1, n1+1, 0 );
   g.addedge( 0, n-1, 0 );
   return g;
 }

// -------------------------  Pn ----------------------------------------------  
 static Graph generate_Pn( int n ){
   Graph g = new Graph( n );
   for( int n1 = 0; n1 < n-1; n1++ )
       g.addedge( n1, n1+1, 0 );
   return g;
 }


// -------------------------  Wn ----------------------------------------------  
  static Graph generate_Wn( int n ){
   Graph g = new Graph( n );

   for( int n1 = 1; n1 < n-1; n1++ ){
     g.addedge( 0,  n1, 0 );
     g.addedge( n1, n1+1, 0 );
   }
   g.addedge( 0, n-1, 0 );
   g.addedge( 1, n-1, 0 );

   for( int i = 0; i < n; i++ )
    Arrays.sort( g.edge[i], 0, g.dg[i] );
   return g;
 }
  
// -------------------- R A N D O M   P A T H ---------------------------------
 static Graph generate_rand_Pn( int n, int seed ){
   Random ra = new Random( seed );
   Graph g = new Graph( n );
   int [] perm = Graph.randPermutation( n, seed+1 );  // use another seed
   for( int i = 0; i < n-1; i++ )
       g.addedge( perm[i], perm[i+1], 0 );
   return g;
 }
// -------------------- R A N D O M   G R A P H -------------------------------
  static Graph randomGraph( int n, int m, int minW, int maxW, int seed ){
    Graph g = new Graph( n );
    g.addRandomEdges( m, seed );
    g.setRandWeights( minW, maxW, seed );
    return g;
  }

// -------------------- R A N D O M   G R A P H -------------------------------
  static Graph randomConnectedGraph( int n, int m, int minW, int maxW, int seed ){
    Graph g = Graph.generate_rand_Pn( n, seed );
    g.addRandomEdges( m - (g.N-1) , seed );
    g.setRandWeights( minW, maxW, seed );
    return g;
  }

  // -------------------- R A N D O M   E D G E S -----------------------------
  void addRandomEdges( int m, int seed ){
    if( m <= 0 ) return;
    long newM = Math.min( (long)M + m, ((long)N*(N-1))/2 );
    
    int j, n1, n2;
    Random ra = new Random( seed );
    
    while( M < newM ){
      n1 = ra.nextInt( N );
      n2 = ra.nextInt( N );
      if ( n1 == n2 )continue;
      // add if edge does not exist yet, slow check :-(
      if( dg[n1] < dg[n2] ){
        for( j = 0; j < dg[n1]; j++ )
          if( edge[n1][j] == n2 )break;
        if( j >= dg[n1] ) // n2 is not a neighbour of n1
          addedge( n1, n2, 0 );
      }
      else {
        for( j = 0; j < dg[n2]; j++ )
          if( edge[n2][j] == n1 )break;
        if( j >= dg[n2] )
            addedge( n1, n2, 0 );
      }
    } // add all edges  
  }
  
// -------------------- R A N D O M   W E I G H T S ---------------------------
  void setRandWeights( int minWeight, int maxWeight, int seed ){
    Random ra = new Random( seed );
    int k, neigh;
    for( int i = 0 ; i < N; i++ )
      for( int j = 0; j < dg[i]; j++ ){
        neigh = edge[i][j];
        if( i < neigh ) {
          k = 0; 
          while( edge[neigh][k] != i ) k++;
          w[i][j] = w[neigh][k] = minWeight+ ra.nextInt( maxWeight-minWeight+1 );
        }
      }
  }
  
// -------------------- R A N D O M   P E R M U T A T I O N -------------------
  static int[] randPermutation( int n, int seed ){
    int [] p = new int[n];
    for( int i = 0; i < n; i++ ) p[i] = i;
    int x, j;
    Random ra = new Random( seed );
    for( int i = n-1; i > 0 ; i-- ){
      j = ra.nextInt( i+1 );
       x = p[i]; p[i] = p[j]; p[j] = x;
    }
    return p; 
  }
  

static void list (int [] a) {
  for( int x : a )
    System.out.printf("%2d ", x);
  System.out.printf("\n");
} 

static void listEdgeArr (int [] a) {
  for( int i = 0; i < a.length; i += 2 )
    System.out.printf( "[%d %d] ", a[i], a[i+1] );
  System.out.printf( "\n" );
} 

static void listEdgePred (int [] pred) {
  for( int i = 0; i < pred.length; i++ )
    if( i != pred[i] )
      System.out.printf( "[%d %d] ", i, pred[i]  );
  System.out.printf( "\n" );
} 


}