// O(M lg N)
// punem in heap noduri
// e nevoie de vectorul poz pentru a nu pastra N-uri
// Prim mai are si rezolvare de complexitate O(N^2)

#include <fstream>
#include <vector>
using namespace std;

const int Nmax = 200011;
const int Mmax = 400011;

#define val first
#define v1 second.first
#define v2 second.second

typedef pair<int, pair<int,int> > Grupe;
typedef Grupe Heap[Nmax];

Grupe Null;

int Apm[Nmax];
int N,M,Size,Ans;
Heap H;
int Poz[Nmax];
vector< pair<int,int> > A[Nmax];
vector< pair<int,int> > Aux;
vector< pair<int,int> > Sol;

ifstream F("apm.in");
ofstream G("apm.out");

void DownHeap(Heap a, int n , int k)
{
	int p;
	p=1;
	while (p)
	{
		p=0;
        if (2*k<=n) 
		{
            p=2*k; 
            if ( (2*k+1<=n) && (a[2*k+1].val<a[2*k].val) ) 
                p++; 
            if (a[p].val >= a[k].val)
                p=0;
        }
        if (p) 
		{
			swap(Poz[a[k].v2],Poz[a[p].v2]);
            swap(a[k].val,a[p].val);
            swap(a[k].v1,a[p].v1);
            swap(a[k].v2,a[p].v2);
			k=p;
        }
	}
}

void UpHeap(Heap a, int n, int k) 
{
	int p=a[k].val;
	int p3=a[k].v1;
	int p4=a[k].v2;
	while ( (k>1) && (p<a[k/2].val) ) 
	{
		swap(Poz[p4],Poz[a[k/2].v2]);
		a[k].val=a[k/2].val;
		a[k].v1=a[k/2].v1;
		a[k].v2=a[k/2].v2;
		k=k/2;
	}
   a[k].val=p;
   a[k].v1=p3;
   a[k].v2=p4;
}

void Earse(Heap a, int& n, int k) 
{
    swap(Poz[a[k].v2],Poz[a[n].v2]); 
    swap(a[k].val,a[n].val); 
    swap(a[k].v1,a[n].v1); 
    swap(a[k].v2,a[n].v2); 
	
	int ok=1; if ( k==n ) ok=0;
	
	n--;
	Poz[a[n+1].v2]=0;
	a[n+1]=Null;
    
	if ( ok && (k>1) && (a[k].val<a[k/2].val) ) 
        UpHeap(a,n,k); 
	else                          
        DownHeap(a,n,k);
}

void Insert(Heap a, int& n, int one,int two , int three) 
{
    a[++n].val=one;
    a[n].v1=two;
    a[n].v2=three;
	
	Poz[a[n].v2]=n;
    UpHeap(a, n, n); 
}

void Insert_Neighbour( int nod )
{
	Apm[nod]=1;
	
	while ( A[nod].size() )
	{
		Aux.push_back( A[nod].back() );
		if ( !Apm[ A[nod].back().first ] )
		{
			if ( ! Poz[ A[nod].back().first ] )
				Insert(H,Size, A[nod].back().second , nod , A[nod].back().first  );
			else
				if ( A[nod].back().second < H[ Poz[ A[nod].back().first ] ].val) 
				{
					Earse(H,Size,Poz[ A[nod].back().first ]);
					Insert(H,Size, A[nod].back().second , nod , A[nod].back().first  );
				}
		}
		A[nod].pop_back();
	}
	while ( Aux.size() )
	{
		A[nod].push_back( Aux.back() );
		Aux.pop_back();
	}
}

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{
		int x,y,cost;
		F>>x>>y>>cost;
		A[x].push_back( make_pair( y , cost ) );
		A[y].push_back( make_pair( x , cost ) );
	}
	
	Insert_Neighbour( 1 );
	
	for (int i=1;i<N;++i)
	{
		while ( Apm[ H[1].v2 ] ) 
			Earse( H, Size , 1 );
		
		int value = H[1].val ;
		int start = H[1].v1 ;
		int endin = H[1].v2 ;
		
		Earse( H, Size , 1 );
		Insert_Neighbour( endin );
		
		Sol.push_back( make_pair(start,endin) );
		Ans+= value;
	}
	
	G<<Ans<<'\n';
	for ( G<<Sol.size()<<'\n' ; Sol.size() ; Sol.pop_back() )
		G<<Sol.back().first<<' '<<Sol.back().second<<'\n';
}