#include <fstream>
#include<algorithm>
  
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{int x, y, cost;};

int n,m;
muchie muchii[400001];
int d[400001], T[200001], G[200001];

int cauta(int x)
{
	int R,aux;
	
	for(R=x;T[R]!=R;R=T[R]);
                  
	return R;
}
void uneste(int x,int y)
{
	if(G[x]>G[y])
		T[y]=x;
	else 
		T[x]=y;
	if(G[x]==G[y])
		G[y]++;
}
  
int crt(int a,int b)
{
	return muchii[a].cost<muchii[b].cost;
}

int main()
{
    int i;
    f>>n>>m;
	
    for(i=1;i<=m;i++)
	{
		f>>muchii[i].x;
		f>>muchii[i].y;
		f>>muchii[i].cost;
	}
	
    for(i=1;i<=n;i++)
	{
		T[i]=i;
		G[i]=1;
	}
  
    for(i=1;i<=m;i++)
		d[i]=i;
	
    sort(d+1,d+m+1,crt);
	
    int c=0, nrm=0;
    int care[200000];
	
    for(i=1;i<=m;i++)
	{
		int a,b;
          a = cauta(muchii[d[i]].x);
		  b = cauta(muchii[d[i]].y);
          if( a != b)
		  {
			uneste(a,b);
			c+=muchii[d[i]].cost;
			care[++nrm]=d[i];}
        }
	
    g<<c<<"\n";
    g<<nrm<<"\n";
	
    for(i=1;i<=nrm;i++)
        g<<muchii[care[i]].x<<" "<<muchii[care[i]].y<<"\n";
	
	return 0;
}