1. #include <fstream>  
   2. #define MAX 200000  
   3. using namespace std;  
   4.   
   5.   
   6. int n, m;  
   7. struct muchie{  
   8.     int v1, v2;  
   9.     int val;  
  10. };  
  11.   
  12. muchie a[MAX];  
  13. muchie arb[MAX];  
  14. int p[MAX];  
  15. int h[MAX];  
  16. int cost;  
  17.   
  18.   
  19. ifstream fin("apm.in");  
  20. ofstream fout("apm.out");  
  21. void Read();  
  22. void Sort(int ,int);  
  23. void Init();  
  24. int Cauta(int);  
  25. void Unire(int, int);  
  26. void Afis();  
  27. void Kruskal();  
  28.   
  29.   
  30.   
  31.   
  32.   
  33. int main()  
  34. {  
  35.     Read();  
  36.     Kruskal();  
  37.     Afis();  
  38.       
  39.       
  40.     fin.close();  
  41.     fout.close();  
  42.     return 0;  
  43. }  
  44.   
  45. void Read()  
  46. {  
  47.     fin >> n;  
  48.     fin >> m;  
  49.     for (int i = 1; i<=m; i++)  
  50.     {  
  51.         fin >> a[i].v1;  
  52.         fin >> a[i].v2;  
  53.         fin >> a[i].val;  
  54.     }  
  55. }  
  56.   
  57. void sort(int x,int y)    
  58. {    int i,j,p;    
  59.      muchie aux;    
  60.      if(x<y)    
  61.       {  i=x-1;    
  62.      j=y+1;    
  63.      p=a[(x+y)/2].val;    
  64.      while(i<j)    
  65.      {   do i++; while(a[i].val<p);    
  66.          do j--; while(a[j].val>p);    
  67.          if(i<j) {  aux=a[i];    
  68.                 a[i]=a[j];    
  69.                 a[j]=aux;    
  70.              }    
  71.      }    
  72.      sort(x,i-1);    
  73.      sort(j+1,y);    
  74.       }    
  75. }    
  76.   
  77. void Init()  
  78. {  
  79.     for (int i = 1; i<=n; i++)  
  80.     {  
  81.         p[i] = i;  
  82.         h[i] = 0;  
  83.     }  
  84. }  
  85.   
  86. void Unire(int x, int y)  
  87. {  
  88.     if (h[x] > h[y])  
  89.     {  
  90.         p[y] = x;  
  91.     }  
  92.     else  
  93.     {  
  94.         p[x] = y;  
  95.         if (h[x] == h[y]) ++h[y];  
  96.     }  
  97. }  
  98.   
  99. int Cauta(int x)  
 100. {  
 101.     if (x != p[x]) p[x] = Cauta(p[x]);  
 102.     return p[x];  
 103. }  
 104.   
 105. void Kruskal()  
 106. {  
 107.     sort(1,m);  
 108.     int k = 0;  
 109.     Init();  
 110.       
 111.     for (int i = 1; i <= m; i++)  
 112.     {  
 113.         int r1 = Cauta(a[i].v1);  
 114.         int r2 = Cauta(a[i].v2);  
 115.         //fout << a[i].v1 << " " << a[i].v2 << "\n";  
 116.         if (r1 != r2)  
 117.         {  
 118.             cost += a[i].val;  
 119.             arb[++k] = a[i];  
 120.             Unire(r1, r2);  
 121.             if (k == n-1) break;  
 122.         }  
 123.     }  
 124. }  
 125.   
 126. void Afis()  
 127. {  
 128.     fout << cost << "\n";  
 129.     fout << n-1 << "\n";  
 130.     for (int i = 1; i <= n-1; i++)  
 131.     {  
 132.         fout << arb[i].v1 << " " << arb[i].v2 << "\n";  
 133.     }  
 134. }                      
 135.               
 136.                   
 137.                           
 138.               
 139.       
 140.       
 141.   
 142.