# include <fstream>
 # include <algorithm>
 
 # define dim 400005
 # define dim2 200005
 
 using namespace std;
 
 ifstream f("apm.in");
 ofstream g("apm.out");
 
 struct arbore
 {
	 int n1, n2, c;
 };
 
 int n, m;
 arbore a[ dim ];
 int c[ dim2 ], sol[ dim2 ], costmin, cnt;
 
 int cmp( arbore a, arbore b )
 {
	 return a.c < b.c;
 }
 
 void citire()
 {
	 int i;
	 
	 f >> n >> m;
	 for ( i = 1 ; i <= m ; i++ )
		 f >> a[ i ].n1 >> a[ i ].n2 >> a[ i ].c;
 }
 
 void conex()
 {
	 int i;
	 for ( i = 1 ; i <= n ; i++ )
		 c[ i ] = i;
 }
 
 void leaga( int x, int y )
 {
	 c[ x ] = y;
 }
 
 int cauta( int x )
 {
	 int r = x, y;
	 
	 while ( c[ r ] != r )
		 r = c[ r ];
	 
	 while ( c[ x ] != x )
	 {
		 y = c[ x ];
		 c[ x ] = r;
		 x = y;
	 }
	 
	 return r;
 }
 
 void rezolva()
 {
	 int i, n1, n2;
	 sort( a + 1, a + m + 1, cmp );
	 
	 for ( i = 1 ; i <= m && cnt < n ; i++ )
	 {
		 n1 = cauta( a[ i ].n1 );
		 n2 = cauta( a[ i ].n2 );
		 
		 if ( n1 != n2 )
		 {
			 cnt ++;
			 sol[ cnt ] = i;
			 costmin = costmin + a[ i ].c;
			 leaga( n1, n2 );
		 }
	 }
 }
 
 void afiseaza()
 {
	 int i;
	 g << costmin << "\n";
	 g << cnt << "\n";
	 for ( i = 1 ; i <= cnt ; i++ )
		 g << a[ sol[ i ] ].n1 << " " << a[ sol[ i ] ].n2 << "\n";
 }
 
 int main()
 {
	 citire();
	 conex();
	 rezolva();
	 afiseaza();
	 return 0;
 }