#include<fstream>
#include<vector>
#include<iostream>
using namespace std;
///////////////////////
#define MaxBuffer 8192
char buffer[MaxBuffer];
int bufferIndex=-1;
///////////////////////
vector <pair <int,int> > a[200100],sol;
int n,sum,tata[200100],poz[200100],heap[400100],V[200100],inf=2000000000,nr=1;
inline void read( istream& in,  int& x )
{
      if( -1 == bufferIndex )
      {
          in.read( buffer, MaxBuffer );
          bufferIndex=0;    
      }
      while( buffer[bufferIndex] < '0' || buffer[bufferIndex] > '9' ) 
           if( ++bufferIndex == MaxBuffer )
           {
              bufferIndex=0;
              in.read( buffer, MaxBuffer );
           }
     for( x=0; buffer[bufferIndex] >= '0' && buffer[bufferIndex] <= '9'; )
     {
          x=x*10+buffer[bufferIndex]-'0';
          if( ++bufferIndex == MaxBuffer )
          {
              bufferIndex=0;
              in.read( buffer, MaxBuffer );
          }
     }
}
void push(int nod) {
	int fiu=nod;nod=0;
	while(fiu!=nod) {
		nod=fiu;
		if(2*nod<nr&&V[heap[fiu]]>V[heap[2*nod]]) fiu=2*nod;
		if(2*nod+1<nr&&V[heap[fiu]]>V[heap[2*nod+1]]) fiu=2*nod+1;
		swap(heap[nod],heap[fiu]);
		swap(poz[heap[nod]],poz[heap[fiu]]);
		}
}
void pop(int nod) {
	while(nod/2&&V[heap[nod]]<V[heap[nod/2]]) {
		swap(heap[nod],heap[nod/2]);
		swap(poz[heap[nod]],poz[heap[nod/2]]);
		nod/=2;
	}
}
int radacina_heap() {
	int nod=heap[1];
	heap[1]=heap[--nr];
	poz[heap[1]]=poz[heap[nr]];
	push(1);
	poz[nod]=0;
	return nod;
}
void introdu_apm(int nod) {
	int i,m=a[nod].size(),vecin;
	for(i=0;i<m;i++) {
		vecin=a[nod][i].first;
		if(V[vecin]>a[nod][i].second&&poz[vecin]) {
			V[vecin]=a[nod][i].second;
			tata[vecin]=nod;
			pop(poz[vecin]);
			}
		}
}
void citire() {
	int i,x,y,c,m;
	ifstream in("apm.in");
	//in>>n>>m;
	read(in,n);read(in,m);
	for(i=0;i<m;i++) {
		//in>>x>>y>>c;
		read(in,x);read(in,y);read(in,c);
		a[x].push_back(pair<int,int>(y,c));
		a[y].push_back(pair<int,int>(x,c));
		}
	in.close();
}
void afis() {
	int i,m=sol.size();
	ofstream out("apm.out");
	out<<sum<<'\n'<<m<<'\n';
	for(i=0;i<m;i++)
		out<<sol[i].first<<" "<<sol[i].second<<'\n';
	out.close();
}
int main() {
	int i,nod;
	long long clo=clock();
	citire();
	cout<<"citire    : "<<clock()-clo<<" ms\n";clo=clock();
	for(i=2;i<=n;V[i++]=inf);
	for(i=2;i<=n;heap[nr]=i,poz[i++]=nr++);
	introdu_apm(1);
	for(i=1;i<n;i++) {
		nod=radacina_heap();
		sum+=V[nod];
		sol.push_back(pair<int,int>(nod,tata[nod]));
		introdu_apm(nod);
		}
	cout<<"terminare : "<<clock()-clo<<" ms\n";clo=clock();
	afis();
	cout<<"afisare   : "<<clock()-clo<<" ms\n";
	return 0;
}