1. #include<iostream>
  2. using namespace std;
  3.  
  4. void make(int n,int parent[],int size[])
  5. {
  6.     parent[n] = n;
  7.     size[n] = 1;
  8. }
  9. int find(int v ,int parent[])
  10. {
  11.     if(parent[v] == v)
  12.     return v;
  13.  
  14.     else
  15.     return parent[v] = find(parent[v],parent);
  16. }
  17. void Union(int v1,int v2,int parent[],int size[])
  18. {
  19.     v1 = find(v1,parent);
  20.     v2 = find(v2,parent);
  21.  
  22.     if(v1 != v2)
  23.     {
  24.         if(size[v1] > size[v2])
  25.         {
  26.             parent[v2] = v1;
  27.             size[v1] += size[v2];
  28.         }
  29.         else
  30.         {
  31.             parent[v1] = v2;
  32.             size[v2] += size[v1];
  33.         }      
  34.     }
  35. }
  36. struct Edges
  37. {
  38.     int v1,v2;
  39.     int weight;
  40. };
  41. int compare(const void* ptr1, const void *ptr2)
  42. {
  43.     Edges *p1 = (Edges*)ptr1;
  44.     Edges *p2 = (Edges*)ptr2;
  45.  
  46.     return ((p1->weight) - (p2->weight));
  47. }
  48.  
  49. int main()
  50. {
  51.     int m,n;
  52.     cin>>m>>n;
  53.     int parent[n];
  54.     int size[n];
  55.     for(int i = 1; i<=n ; ++i)
  56.     {
  57.         make(i,parent,size);
  58.     }
  59.     Edges *EdgeArr = new Edges[m];
  60.     for(int i = 0 ; i < m ; ++i)
  61.     {
  62.         cin>>EdgeArr[i].v1;
  63.         cin>>EdgeArr[i].v2;
  64.         cin>>EdgeArr[i].weight;
  65.     }
  66.  
  67.  
  68.     qsort(EdgeArr,m,sizeof(struct Edges),compare);
  69.  
  70.     for(int i = 0 ; i < m ; ++i)
  71.     {
  72.         Edges edg = EdgeArr[i];
  73.         int v1 = edg.v1;
  74.         int v2 = edg.v2;
  75.         int wt = edg.weight;
  76.  
  77.         if(find(v1,parent) == find(v2,parent))
  78.         continue;
  79.  
  80.         Union(v1,v2,parent,size);
  81.         cout<< v1 << " " << v2 <<endl;
  82.     }
  83.  
  84. }
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.    
  92.  
  93.